社区讨论

为什么我的分块过不了?

P3374【模板】树状数组 1参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mijkxrdi
此快照首次捕获于
2025/11/29 08:55
3 个月前
此快照最后确认于
2025/11/29 19:55
3 个月前
查看原帖
树状数组过了,想试试分块却样例都过不了求调代码
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[100010], sum[100010], add[100010];
int L[100010], R[100010];
int pos[100010];
int n, m;
void change (int l, int r, int d) {
	int p = pos[l], q = pos[r];
	if (p == q) {
		for (int i = l; i <= r; i ++) a[i] += d;
		sum[p] += d * (r - l + 1);
	} else {
		for (int i = p + 1; i <= q - 1; i ++) add[i] += d;
		for (int i = l; i <= R[p]; i ++) a[i] += d;
		sum[p] += d * (R[p] - l + 1);
		for (int i = L[q]; i <= r; i ++) a[i] += d;
		sum[q] = d * (r - L[q] + 1);
	}
}
int ask (int l, int r) {
	int p = pos[l], q = pos[r], ans = 0;
	if (p == q) {
		for (int i = l; i <= r; i ++) ans += a[i];
		ans += add[p] * (r - l + 1);
	} else {
		for (int i = p + 1; i <= q - 1; i ++)
			ans += sum[i] + add[i] * (R[i] - L[i] + 1);
		for (int i = l; i <= R[p]; i ++) ans += a[i];
		ans += add[p] * (R[p] - l + 1);
		for (int i = L[p]; i <= r; i ++) ans += a[i];
		ans += add[p] * (r - L[p] + 1);
	}
	return ans;
}
signed main () {
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	int t = sqrt(n);
	for (int i = 1; i <= t; i ++) {
		L[i] = (i - 1) * sqrt(n) + 1;
		R[i] = i * sqrt(n);
	}
	if (R[t] > n) t ++, L[t] = R[t - 1] + 1, R[t] = n;
	for (int i = 1; i <= t; i ++) {
		for (int j = L[i]; j <= R[i]; j ++) {
			pos[j] = i;
			sum[i] += a[j];
		}
	}
	while (m --) {
		int op, x, y, k;
		cin >> op;
		if (op == 1) {
			cin >> x >> k;
			a[x] += k;
    		sum[ pos[x] ] += k;
		} else {
			cin >> x >> y;
			cout << ask(x, y) << endl;
		}
	}
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...