題目連結：https://www.luogu.com.cn/problem/P3870
涉及操作：
- 區間取反；
- 區間和。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, m, blo, a[maxn], bl[maxn], sum[505], tag[505];
// 将區間[l,r]取反
void update(int l, int r) {
for (int i = l; i <= min(r, bl[l]*blo); i ++) {
sum[bl[i]] -= a[i] ^ tag[bl[i]];
a[i] ^= 1;
sum[bl[i]] += a[i] ^ tag[bl[i]];
}
if (bl[l] != bl[r]) {
for (int i = (bl[r]-1)*blo+1; i <= r; i ++) {
sum[bl[i]] -= a[i] ^ tag[bl[i]];
a[i] ^= 1;
sum[bl[i]] += a[i] ^ tag[bl[i]];
}
}
for (int i = bl[l]+1; i < bl[r]; i ++)
tag[i] ^= 1, sum[i] = blo - sum[i];
}
// 區間[l,r]求和
int query(int l, int r) {
int res = 0;
for (int i = l; i <= min(r, bl[l]*blo); i ++)
res += a[i] ^ tag[bl[i]];
if (bl[l] != bl[r]) {
for (int i = (bl[r]-1)*blo+1; i <= r; i ++)
res += a[i] ^ tag[bl[i]];
}
for (int i = bl[l]+1; i < bl[r]; i ++) {
res += sum[i];
}
return res;
}
int main() {
cin >> n >> m;
blo = sqrt(n);
for (int i = 1; i <= n; i ++)
bl[i] = (i - 1) / blo + 1;
while (m --) {
int op, x, y;
cin >> op >> x >> y;
assert(1 <= x && x <= y && y <= n);
if (op == 0) update(x, y);
else cout << query(x, y) << endl;
}
return 0;
}