重金5块钱求大佬帮忙看一下下列分块代码?
查看原帖
重金5块钱求大佬帮忙看一下下列分块代码?
291976
quanjun楼主2021/11/19 14:43

本题我是用数列分块做的。
其中, sum[i]sum[i] 表示第 ii 个分块的元素和,tag[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;
}
2021/11/19 14:43
加载中...