Tóm tắt đề bài

Cho mảng nhị phân \(a_1..a_n\) (đồng xu \(0/1\)), có \(q\) truy vấn:

• Loại 1: 1 l r — lật tất cả đồng xu trong đoạn \([l,r]\) (\(a_i \leftarrow 1-a_i\)).
• Loại 2: 2 l r — đếm số đoạn con \((x,y)\) với \(l \le x \le y \le r\) sao cho đoạn \([x,y]\) xen kẽ, tức \(a_i \ne a_{i+1}\) với mọi \(x \le i < y\).

Cần trả lời online với \(n,q \le 2\cdot 10^5\).

Phân tích

• Một đoạn \([x,y]\) xen kẽ nghĩa là các phần tử liên tiếp luôn khác nhau.
• Nếu xét trực tiếp sẽ khó vì có cập nhật lật đoạn.
• Nhận xét then chốt: điều kiện xen kẽ phụ thuộc vào quan hệ giữa vị trí và giá trị. Ta “chuẩn hoá” để biến “xen kẽ” thành “tất cả bằng nhau”.

Chuẩn hoá mảng

Đặt:

• Nếu \(a\) xen kẽ kiểu 0,1,0,1,... thì \(b\) sẽ toàn \(0\).
• Nếu \(a\) xen kẽ kiểu 1,0,1,0,... thì \(b\) sẽ toàn \(1\).

Suy ra: đoạn \([x,y]\) xen kẽ trong \(a\) khi và chỉ khi đoạn \([x,y]\) trong \(b\) là đoạn toàn phần tử bằng nhau (toàn \(0\) hoặc toàn \(1\)).

Khi lật \(a_i \leftarrow 1-a_i\) thì \(b_i\) cũng bị lật tương ứng: \(b_i \leftarrow 1-b_i\). Vậy truy vấn loại 1 trở thành flip đoạn trên mảng nhị phân \(b\).

Bài toán sau biến đổi

• Update: flip tất cả bit trong \(b[l..r]\).
• Query: trong đoạn \(b[l..r]\), đếm số đoạn con toàn \(0\) hoặc toàn \(1\).

Đếm số đoạn con toàn bằng nhau trong một đoạn có thể làm bằng cách chia thành các “khối” liên tiếp cùng giá trị; nếu độ dài khối là \(k\) thì đóng góp \(k(k+1)/2\). Nhưng khi có flip đoạn, khối thay đổi phức tạp ⇒ dùng segment tree.

Hướng giải quyết

Dùng segment tree + lazy propagation trên mảng \(b\).

Thông tin lưu ở mỗi node

Với một node ứng với đoạn dài cnt, lưu:

• val: số đoạn con toàn bằng nhau trong đoạn này.
• pre[2]: độ dài prefix toàn \(0\) và toàn \(1\).
• suf[2]: độ dài suffix toàn \(0\) và toàn \(1\).
• lazy: cờ flip (0/1) cho lazy propagation.

Ý nghĩa:

• pre[t] là số phần tử đầu đoạn liên tiếp đều bằng \(t\).
• suf[t] là số phần tử cuối đoạn liên tiếp đều bằng \(t\).

Ở lá (một phần tử):

• val = 1 (đoạn con duy nhất là chính nó).
• Nếu phần tử là \(t\) thì pre[t]=suf[t]=1, còn lại mặc định $0`.

Gộp hai node con (merge)

Giả sử gộp trái L và phải R thành P.

1. Tổng số đoạn con toàn bằng nhau:
   • Tất cả đoạn con nằm hoàn toàn trong L: L.val
   • Nằm hoàn toàn trong R: R.val
   • Cắt qua ranh giới: chỉ khi đoạn kết thúc bằng một dãy \(t\) ở L và bắt đầu bằng dãy \(t\) ở R
     • Số cách chọn = L.suf[t] * R.pre[t]

Vì vậy:

1. Tính prefix:
2. Nếu L toàn \(t\) (tức L.pre[t] == L.cnt) thì prefix toàn \(t\) của P kéo dài sang R:

• Ngược lại, prefix của P chính là prefix của L.

• Tính suffix tương tự:

• Nếu R toàn \(t\) (R.suf[t] == R.cnt) thì suffix kéo dài sang L:

Lazy propagation cho phép flip đoạn

Khi flip toàn bộ một node:

• Các đoạn toàn \(0\) trở thành toàn \(1\) và ngược lại.

• Do đó chỉ cần:

• swap(pre[0], pre[1])

• swap(suf[0], suf[1])
• lazy ^= 1

Lưu ý: val không đổi vì số đoạn con “toàn bằng nhau” không phụ thuộc nhãn \(0/1\), chỉ phụ thuộc việc các phần tử bằng nhau.

Khi đẩy lazy xuống con, áp dụng phép swap tương tự cho 2 node con.

Trả lời truy vấn

• Update loại 1: gọi update(l,r) trên segment tree.
• Query loại 2: lấy node đại diện đoạn $[l,r], innode.val`.

Liên hệ với code AC

• Code đọc \(a_i\), sau đó nếu \(i\) chẵn thì a[i] ^= 1 chính là tạo \(b_i = a_i \oplus (i \bmod 2)\).
• Node.val, pre, suf, cnt, lazy đúng như mô tả.
• Hàm merge hiện thực đúng công thức gộp.
• Flip trong update và down chỉ swap pre/suf và bật lazy.

Độ phức tạp

• Mỗi truy vấn update / query chạy trên segment tree: \(O(\log n)\).
• Bộ nhớ: \(O(n)\) cho cây.

Phù hợp với \(n,q \le 2\cdot 10^5\).

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

struct SegmentTree {
    struct Node {
        long long val = 0;     // số đoạn con toàn bằng nhau trong đoạn
        long long pre[2] = {0, 0}; // prefix toàn 0 / toàn 1
        long long suf[2] = {0, 0}; // suffix toàn 0 / toàn 1
        int cnt = 0;           // độ dài đoạn
        int lazy = 0;          // cờ flip
    };

    int n;
    vector<Node> st;
    SegmentTree(int n): n(n) {
        st.resize(4 * n + 1);
    }

    // gộp b (trái) và c (phải) vào a (cha)
    void merge(Node &a, Node &b, Node &c) {
        a.val = b.val + c.val + b.suf[0] * c.pre[0] + b.suf[1] * c.pre[1];
        a.cnt = b.cnt + c.cnt;

        for (int i = 0; i <= 1; i++) {
            if (b.pre[i] == b.cnt) a.pre[i] = b.pre[i] + c.pre[i];
            else a.pre[i] = b.pre[i];
        }

        for (int i = 0; i <= 1; i++) {
            if (c.suf[i] == c.cnt) a.suf[i] = c.suf[i] + b.suf[i];
            else a.suf[i] = c.suf[i];
        }
    }

    void build(vector<int> &a, int id, int l, int r) {
        if (l == r) {
            st[id].val = 1;
            st[id].pre[a[l]] = st[id].suf[a[l]] = 1;
            st[id].cnt = 1;
            return;
        }
        int mid = (l + r) / 2;
        build(a, id * 2, l, mid);
        build(a, id * 2 + 1, mid + 1, r);
        merge(st[id], st[id * 2], st[id * 2 + 1]);
    }

    void down(int id, int l, int r) {
        if (l == r || !st[id].lazy) return;

        for (int child = id * 2; child <= id * 2 + 1; child++) {
            swap(st[child].pre[0], st[child].pre[1]);
            swap(st[child].suf[0], st[child].suf[1]);
            st[child].lazy ^= 1;
        }
        st[id].lazy = 0;
    }

    void update(int id, int l, int r, int u, int v) {
        if (r < u || l > v) return;
        if (u <= l && r <= v) {
            swap(st[id].pre[0], st[id].pre[1]);
            swap(st[id].suf[0], st[id].suf[1]);
            st[id].lazy ^= 1;
            return;
        }
        down(id, l, r);
        int mid = (l + r) / 2;
        update(id * 2, l, mid, u, v);
        update(id * 2 + 1, mid + 1, r, u, v);
        merge(st[id], st[id * 2], st[id * 2 + 1]);
    }

    Node query(int id, int l, int r, int u, int v) {
        if (r < u || v < l) return Node(); // node rỗng
        if (u <= l && r <= v) return st[id];

        down(id, l, r);
        int mid = (l + r) / 2;
        Node left = query(id * 2, l, mid, u, v);
        Node right = query(id * 2 + 1, mid + 1, r, u, v);
        Node res;
        merge(res, left, right);
        return res;
    }
};

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

    int n, q;
    cin >> n >> q;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        // biến đổi b_i = a_i XOR (i mod 2)
        if (i % 2 == 0) a[i] ^= 1;
    }

    SegmentTree seg(n);
    seg.build(a, 1, 1, n);

    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1) {
            seg.update(1, 1, n, l, r);
        } else {
            cout << seg.query(1, 1, n, l, r).val << "\n";
        }
    }
    return 0;
}