Lời giải được cung cấp bởi bạn lto5

Tóm tắt đề bài

Cho dãy nhị phân ~a~ có ~n~ bit. Ban đầu tất cả các bit đều là ~0~. Xử lí hai loại truy vấn:

• ~0\ l\ r~: đảo tất cả các bit trong đoạn ~[l,r]~, từ ~0~ sang ~1~ và ngược lại
• ~1\ l\ r~: tìm số bit ~1~ trong đoạn ~[l,r]~

Subtask 1

Rất dễ dàng, các bạn chỉ cần thực hiện mỗi truy vấn trong ~O(n)~. Độ phức tạp tổng là ~O(qn)~

for query:
    if type == 0:
        for i = l to r:
            a[i] ^= 1
    else:
        ans = 0
        for i = l to r:
            ans += a[i]
        print(ans)

Subtask 2

Với giới hạn ~n, q \leq 10^5~, có rất nhiều cách làm cho bài toán này. Ở đây mình xin giới thiệu ba cách:

Segment Tree

Đây là một bài toán cơ bản, áp dụng nguyên lí "cập nhật lười".

Với mỗi nút ~[l,r]~ trên cây, ta lưu một mảng ~st_{id}~ thể hiện tổng của đoạn ~a[l:r]~. Ban đầu, tất cả các nút đều có giá trị ~0~.

Ta lưu thêm một mảng ~lazy_i~ thể hiện xem nút ~i~ đã được "tác động bao nhiêu lần". Lưu ý, theo tính chất của phép xor, thì nếu ta tác động chẵn lần, thì xem như là không làm gì. Vậy mảng ~lazy~ ta chỉ cần lưu với giá trị ~0/1~.

Với mỗi truy vấn cập nhật đoạn ~(u, v)~, ta tìm đến các nút ~id~ quản lí đoạn ~[l,r]~ mà nằm gọn trong đoạn ~[u,v]~, sau đó gán:

• ~lazy_{id} = (lazy_{id} + 1) \mod 2~
• ~st_{id} = r-l+1-st_{id}~

Nghĩa là khi tiến hành tác động một đoạn, thì các bit ~0~ trở thành bit ~1~, và bit ~1~ trở thành bit ~0~. Như vậy, số lượng bit ~0~ và ~1~ sẽ hoán đổi cho nhau. Mà số lượng bit ~1~ là ~st_{id}~ và ~0~ là ~r-l+1-st_{id}~, nên ta rút ra được công thức như trên.

Hàm lấy giá trị một đoạn thì ta có thể cài đặt giống như mọi bài toán lazy khác.

Cuối cùng, ta cần cài đặt hàm push để "đẩy" giá trị lười từ cha xuống con. Nếu ~lazy_{id}=1~, nghĩa là đoạn này buộc phải thay đổi do đã có lẻ lần tác động lên đoạn này. Ta tiến hành thay đổi giá trị nút trái và phải của ~id~ như trên. Ngược lại, ta không thay đổi bất kì một giá trị nào khác. Sau khi hoàn thành, ta gán ~lazy_{id}=0~

Độ phức tạp: ~O(nlogn)~

Chia căn

Bài toán này cũng có thể giải quyết bằng việc chia block kết hợp với phương pháp lazy như ở segment tree. Tác giả xin phép không đi chi tiết vào phương pháp này, bạn đọc có thể tham khảo tại VNOI Wiki.

Triển khai mẫu: https://ideone.com/E3Newt

Độ phức tạp: ~O(n \sqrt{n})~

Bitset

Ta duy trì một bitset ~A~ thể hiện mảng ~a~.

• Để lấy các bit có vị trí nằm trên đoạn ~[l,r]~ của ~a~, thay vì ta duyệt từ ~l~ đến ~r~ như thông thường, ta sẽ sử dụng một trick xử lí trên bit để tối ưu. Cụ thể, thay vì nghĩ rằng ta cần giữ lại các bit, ta sẽ "xoá" các bit thuộc đoạn ~[0,l)~ và ~[r+1,n)~. Để xoá các bit có vị trí thuộc đoạn ~[0,l)~, ta thực hiện phép shift ~a~ sang trái ~l~ bit, lúc này các bit đã bị xoá nhưng vị trí đã bị thay đổi, ta chỉ cần shift ~a~ sang phải lại ~l~ bit để trả lại vị trí ban đầu. Tương tự, để xoá đoạn ~[r+1,n)~, ta chỉ cần shift left ~n-r-1~ bước sau đó lại shift right ~n-r-1~ bước. Trong std::bitset đã hỗ trợ một hàm bitset.count() để đếm số bit, còn nếu ta tự cài đặt thì nên dùng hàm __builtin_popcountll() để đảm bảo tốc độ.

Ví dụ minh hoạ một truy vấn

• Để thực hiện phép toán xor một đoạn, ta chuẩn bị một bitset ~full~ độ dài ~n~, và gồm toàn các bit ~1~. Với mỗi truy vấn, ta dùng trick trên để lấy ra các bit thuộc đoạn ~[l,r]~ của ~full~, tạm đặt là ~B~. Lúc này, các bit ngoài đoạn ~[l,r]~ sẽ mang toàn giá trị ~0~, vậy phép xor ở các vị trí này sẽ không bị ảnh hưởng đến giá trị ban đầu. Ta chỉ cần tiến hành lấy ~A~ xor với ~B~ là xong.

Độ phức tạp khoảng ~O(\frac{nq}{64}) \thickapprox 1.5 \times 10^8~. Tuy nhiên do các phép toán trên bit chạy rất nhanh, nên solution vẫn có thể AC. Cụ thể, cài đặt của mình chỉ mất ~0.8s~ để chạy trên bộ test chính thức, mặc dù mình chưa cần dùng đến các phương pháp tối ưu cao hơn như pragma hay tối ưu sử dụng avx instruction. Các bạn cũng có thể tự tối ưu bằng việc tự implement bitset bằng kiểu số nguyên ~64~ bit (unsigned long long...)

Cài đặt: https://ideone.com/kvQPZl

#include <bits/stdc++.h>
#define BIT(x, i) (((x)>>(i))&1)
#define MASK(i) (1LL<<(i))
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define discrete(x) x.resize(unique(all(x)) - x.begin())
#define mp make_pair
#define pb push_back
#define TASK "test"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vll;
typedef vector<pll> vlll;

template<typename T1, typename T2> bool mini(T1 &a, T2 b) {if(a>b) a=b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b) {if(a<b) a=b; else return 0; return 1;}
template<typename T1> T1 abs(T1 a) {if(a<0) a*=-1; return a;}

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll h){return l + ll(rd()) * rd() %(h-l+1);}

struct Input
{
    void read()
    {
        cin >> n >> q;
        for(int i = 0; i < q; i++)
        {
            int type, l, r;
            cin >> type >> l >> r;
            queries.push_back({(QueryType)type, l, r});
        }
    }

    enum QueryType
    {
        UPDATE = 0,
        QUERY = 1
    };

    struct Query
    {
        QueryType type;
        int l, r;
    };

    int n, q;
    vector<Query> queries;
};

struct Output
{
    void print()
    {
        for(int x : ans)
        {
            cout << x << '\n';
        }
    }

    vector<int> ans;
};

class SegmentTree
{
#define left(v) (2*v)
#define right(v) (2*v+1)

public:
    SegmentTree(int n)
    : n(n)
    , st(4*n)
    , lazy(4*n)
    {
        build(1, 0, n-1);
    }

    void update(int l, int r)
    {
        update(1, 0, n-1, l, r);
    }

    int query(int l, int r)
    {
        return query(1, 0, n-1, l, r);
    }

private:
    void build(int v, int tl, int tr)
    {
        if(tl == tr)
        {
            st[v] = 0;
        }
        else
        {
            int tm = (tl + tr) >> 1;
            build(left(v), tl, tm);
            build(right(v), tm+1, tr);
        }
    }

    void push(int v, int tl, int tr)
    {
        if(lazy[v] == 0)
            return;

        st[v] = (tr - tl + 1) - st[v];
        if(tl != tr)
        {
            lazy[left(v)] ^= 1;
            lazy[right(v)] ^= 1;
        }
        lazy[v] = 0;

    }

    void update(int v, int tl, int tr, int l, int r)
    {
        push(v, tl, tr);
        if(l > tr || r < tl)
            return;
        if(l <= tl && tr <= r)
        {
            lazy[v] ^= 1;
            push(v, tl, tr);
            return;
        }
        int tm = (tl + tr) >> 1;
        update(left(v), tl, tm, l, r);
        update(right(v), tm+1, tr, l, r);
        st[v] = st[left(v)] + st[right(v)];
    }

    int query(int v, int tl, int tr, int l, int r)
    {
        push(v, tl, tr);
        if(l > tr || r < tl)
            return 0;
        if(l <= tl && tr <= r)
            return st[v];
        int tm = (tl + tr) >> 1;
        return query(left(v), tl, tm, l, r) + query(right(v), tm+1, tr, l, r);
    }

private:
    int n;
    vector<int> st, lazy;

#undef left
#undef right
};

class Solver
{
public:
    Solver(Input &input, Output &output)
    : input(input)
    , output(output)
    {
        solve();
    }

    void solve()
    {
        SegmentTree st(input.n);
        for(Input::Query &query : input.queries)
        {
            if(query.type == Input::UPDATE)
            {
                st.update(query.l, query.r);
            }
            else
            {
                output.ans.push_back(st.query(query.l, query.r));
            }
        }
    }

private:
    Input &input;
    Output &output;
};

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    Input input;
    Output output;

    input.read();
    Solver(input, output);
    output.print();

    return 0;
}