社区讨论
为什么我的分块过不了?
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 条回复,欢迎继续交流。
正在加载回复...