题解 | 区间取反与区间数一

#include<bits/stdc++.h>
#define endl "\n"
#define int long long
using namespace std;
struct node {
    int l, r, cnt, laz;
} tree[500010 * 4];
void slove() {
    int n, q;
    std::cin >> n >> q;
    std::string s;
    std::cin >> s;
    s = ' ' + s;
    auto build = [&](auto&& build, int p, int l, int r)->void{
        tree[p].l = l, tree[p].r = r;
        if (l == r) {
            tree[p].laz = 0;
            tree[p].cnt = (s[l] == '1');
            return ;
        }
        int mid = l + r >> 1;
        build(build, p * 2, l, mid);
        build(build, p * 2 + 1, mid + 1, r);
        tree[p].cnt = tree[p * 2].cnt + tree[p * 2 + 1].cnt;
    };
    auto pushdown = [&](int p)->void{
        if (tree[p].laz) {
            tree[p * 2].cnt = (tree[p * 2].r - tree[p * 2].l + 1 - tree[p * 2].cnt);
            tree[p * 2 + 1].cnt = (tree[p * 2 + 1].r - tree[p * 2 + 1].l + 1 - tree[p * 2 +
                                   1].cnt);
            if (tree[p * 2].laz == 0)tree[p * 2].laz = 1;
            else tree[p * 2].laz = 0;
            if (tree[p * 2 + 1].laz == 0)tree[p * 2 + 1].laz = 1;
            else tree[p * 2 + 1].laz = 0;
            tree[p].laz = 0;
        }
    };
    auto change = [&](auto&& change, int p, int l, int r)->void{
        if (tree[p].l >= l && tree[p].r <= r) {
            tree[p].cnt = (tree[p].r - tree[p].l + 1 - tree[p].cnt);
            if (tree[p].laz == 0)tree[p].laz = 1;
            else tree[p].laz = 0;
            return ;
        }
        pushdown(p);
        int mid = tree[p].l + tree[p].r >> 1;
        if (mid >= l) change(change, p * 2, l, r);
        if (mid < r) change(change, p * 2 + 1, l, r);
        tree[p].cnt = tree[p * 2].cnt + tree[p * 2 + 1].cnt;
    };
    auto qurey = [&](auto&& qurey, int p, int l, int r)->int{
        if (tree[p].l >= l && tree[p].r <= r) return tree[p].cnt;
        pushdown(p);
        int ans = 0;
        int mid = tree[p].l + tree[p].r >> 1;
        if (mid >= l) ans += qurey(qurey, p * 2, l, r);
        if (mid < r) ans += qurey(qurey, p * 2 + 1, l, r);
        return ans;
    };
    build(build, 1, 1, n);
    while (q--) {
        int op, l, r;
        std::cin >> op >> l >> r;
        if (op == 1) {
            change(change, 1, l, r);
        } else std::cout << qurey(qurey, 1, l, r) << endl;
    }
}
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T = 1;
    //std::cin>>T;
    while (T--)    {
        slove();
    }
    return 0;
}

题目明显提示是类似线段树的数据结构了，所以这题其实就是一个查询区间的线段树模板。要注意的一点是懒标记的叠加，如果某一个区间被懒标记标记了偶数次，那么相当于没有翻转操作，这种性质可以将懒标记用异或代替即可。