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

带标记的线段树

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
struct Node {
    int sum;
    bool flip;
} seg[4 * MAXN];
string s;
int n, q;
void apply(int p, int l, int r) {
    seg[p].sum = (r - l + 1) - seg[p].sum;
    seg[p].flip ^= 1;
}
void push(int p, int l, int r) {
    if (!seg[p].flip) return;
    int mid = (l + r) >> 1;
    apply(p << 1, l, mid);
    apply(p << 1 | 1, mid + 1, r);
    seg[p].flip = false;
}
void pull(int p) {
    seg[p].sum = seg[p << 1].sum + seg[p << 1 | 1].sum;
}
void build(int p, int l, int r) {
    if (l == r) {
        seg[p].sum = s[l - 1] - '0';
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pull(p);
}
void update(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        apply(p, l, r);
        return;
    }
    push(p, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) update(p << 1, l, mid, ql, qr);
    if (qr > mid)  update(p << 1 | 1, mid + 1, r, ql, qr);
    pull(p);
}
int query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return seg[p].sum;
    push(p, l, r);
    int mid = (l + r) >> 1;
    int res = 0;
    if (ql <= mid) res += query(p << 1, l, mid, ql, qr);
    if (qr > mid)  res += query(p << 1 | 1, mid + 1, r, ql, qr);
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    cin >> s;
    build(1, 1, n);
    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) update(1, 1, n, l, r);
        else cout << query(1, 1, n, l, r) << '\n';
    }
    return 0;
}