Hướng dẫn giải của Bedao Mini Contest 16 - QUERY


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

~\bf{Subtask 1}~

Trong Subtask này, thuật toán chỉ đơn giản là duyệt mọi phần tử trong đoạn để cập nhật/tính đáp án.

~\bf{Subtask 2}~

Đây là bài toán sử dụng Cây phân đoạn (Segment Tree) kết hợp với kĩ thuật Lazy Update cơ bản.

Tại mỗi node ~st[id]~ sẽ lưu một giá trị ~SUMOR~ là tổng ~OR~ các phần tử trong đoạn mà node đó quản lí. Bên cạnh đó ta cũng phải lưu thêm một biến để thực hiện kĩ thuật Lazy Update.

Cụ thể; ngoài trường giá trị ~SUMOR~ kể trên, ta cần lưu thêm một giá trị là ~LAZY~ với ý nghĩa tất cẳ các phần tử trong đoạn mà node này quản lí được đặt lại bằng ~LAZY~ (Nếu không phần tử nào bị đặt lại thì ~LAZY=-1~):

  • Khi thực hiện truy vấn cập nhật và truy vấn tính đáp án, ta dồn biến ~LAZY~ xuống hai con và reset biến ~LAZY~ về ~1~ trước khi gọi đệ qui.
  • Khi gặp node cần cập nhật, ta ghi đè giá trị cần thay đổi vào biến ~LAZY~ và biến ~SUMOR~ của node đó.

~\bf{Subtask 3}~

Ta nhận thấy nếu mảng và các truy vấn chỉ gồm các số ~1~ và ~0~, các thao tác loại ~1~ sẽ biến đối dãy số như sau:

  • Nếu ~x=0~, thao tác này tương đương thao tác loại ~2~.
  • Nếu ~x=1~, thao tác này không làm dãy số thay đổi.

Từ đó ta có thể dựng ra ~30~ cây phân đoạn, cây thứ ~i~ sẽ quản lí bit thứ ~i~ của tất cả các số trong dãy. Khi gặp các truy vấn, ta tách các số ra từng bit và xử lí trên mỗi cây như tại Subtask 2.

~\bf{Subtask 4}~ nb Để chương trình chạy nhanh hơn, ta cần tối ưu thuật toán; việc cần làm là giảm số cây phân đoạn sử dụng từ ~30~ xuống còn ~1~ cây. Để có thể làm được như vậy; tại mỗi node sẽ thêm một trường giá trị nữa ngoài ~LAZY~ và ~SUMOR~ là ~LAZYAND~.

Biến này lưu giá trị tổng AND của các số mà những phần tử trong đoạn phải thực hiện phép AND cùng. Tức là nếu tồn tại hai truy vấn làm cho ~a[i] = (a[i]~ AND ~x_1)~ AND ~x_2~, ta sẽ viết ~a[i] = a[i]~ AND ~(x_1~ AND ~x_2)~; khi đó ~x_1~ AND ~x_2~ chính là giá trị ~LAZYAND~.

Trong quá trình cập nhật/truy vấn đáp án, có một vài trường hợp sau xảy ra; và sẽ xử lí như sau:

Ta cập nhật biến ~LAZY~ bởi giá trị ~x~:

  • Biến ~LAZYAND~ sẽ bị reset về ~-1~.
  • ~LAZY~ và ~SUMOR~ sẽ được gán bởi ~x~.

Ta cập nhật biến ~LAZYAND~ bởi ~x~:

  • Nếu biến ~LAZY\neq -1~, thao tác này tương đương với việc cập nhật biến ~LAZY~ bởi giá trị ~LAZY~ AND ~x~.
  • Nếu biến ~LAZY=-1~, ta thay ~SUMOR~ bởi ~(SUMOR~ AND ~x)~ và ~LAZYAND~ bởi ~(LAZYAND~ AND ~x)~.

Khi truyền giá trị từ một node xuống hai con trong quá trình cập nhật và truy vấn; các bạn đẩy giá trị nào xuống trước cũng được, song cần chú ý nếu giá trị ~x=-1~ thì không làm gì cả!

Code mẫu

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}
const int N = 1e6 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

int val[N << 2];
int op[N << 2];
int st[N << 2];
int n,q;

void combine(int id, int t, int v) {
    if (op[id] == -1 || t == 2) {
        op[id] = t, val[id] = v;
    } else {
        val[id] &= v;
    }

    if (op[id] == 1) 
        st[id] &= val[id];
    else 
        st[id] = val[id];
}

void dolazy(int id) {
    if (op[id] == -1) 
        return;
    combine(id << 1, op[id], val[id]);
    combine(id << 1 | 1, op[id], val[id]);
    op[id] = val[id] = -1;
}

void update(int id, int l, int r, int u, int v, int op, int val) {
    if (l > v || r < u)
        return;
    if (l >= u && r <= v) {
        combine(id, op, val);
        return;
    }
    int mid = (l + r) >> 1;
    dolazy(id);
    update(id << 1, l, mid, u, v, op, val);
    update(id << 1 | 1, mid + 1, r , u, v, op, val);
    st[id] = st[id << 1] | st[id << 1 | 1];
}

void update(int l, int r, int op, int val) {
    update(1, 1, n, l, r, op, val);
}

int getor(int id, int l, int r, int u, int v) {
    if (l > v || r < u)
        return 0;
    if (l >= u && r <= v) 
        return st[id];
    int mid = (l + r) >> 1;
    dolazy(id);
    int lnode = getor(id << 1, l, mid, u, v);
    int rnode = getor(id << 1 | 1, mid + 1, r, u, v);
    return lnode | rnode;
}

int getor(int l, int r) {
    return getor(1, 1, n, l, r);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef ONLINE_JUDGE
    // freopen(TASK".inp","r",stdin);
    // freopen(TASK".out","w",stdout);
    #endif
    cin >> n >> q;
    for (int i = 1; i <= 4 * n; i++) 
        op[i] = val[i] = -1;

    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        update(i, i, 2, x);
    }

    while (q--) {
        int op, l, r, x;
        cin >> op >> l >> r;
        if (op <= 2) {
            cin >> x;
            update(l, r, op, x);
        } else{
            cout << getor(l, r) << "\n";
        }
    }
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.