本题我是用数列分块做的。
其中, sum[i] 表示第 i 个分块的元素和,tag[i] 表示整体是否需要取反。检查了半天还是没有检查出来哪里写错了。求大佬帮忙看一下代码并留下联系方式(私信也可),我将发送5块钱红包作为酬谢。
#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;
}
// 区间[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 ++) {
if (tag[i]) res += sum[i];
else res += blo - 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;
}