记录
11:03 2024-2-25
http://poj.org/problem?id=1961
-
线段树
-
树状数组
把区间增加转变为单点增加，利用两个树状数组\(c_0 和 c_1\)
将”C l r d" 转化为
- 在树状数组\(c_0\)中，把位置l上的数加d
- 在树状数组\(c_0\)中，把位置r + 1上的数减d
- 在树状数组\(c_1\)中，把位置l上的数加l * d
- 在树状数组\(c_1\)中，把位置r + 1上的数减(r + 1) * d
建立sum存储a的原始前缀和
将“Q l r” 转化为 1~r 和 1~l-1两部分进行相减
$ (sum[r] + (r + 1) * ask(c_0, r) - ask(c_1, r)) - (sum[l - 1] + l * ask(c_0, l - 1) - ask(c_1, l - 1)) $
点击查看代码
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
int N, Q;
ll a[MAXN], sum[MAXN];
ll c[2][MAXN];
// k表示是哪个树状数组，i表示位置, v表示加入的值
void add(int k, int i, int v) {
while (i <= N){
c[k][i] += v;
i += i & -i;
}
}
// k表示是哪个树状数组，i表示位置
ll ask(int k, int i) {
ll s = 0;
while (i > 0) {
s += c[k][i];
i -= i & -i;
}
return s;
}
int main() {
cin >> N >> Q;
for(int i = 1; i <= N; i++) {
scanf("%lld", &a[i]);
sum[i] = sum[i - 1] + a[i];
}
char c[2];
int l, r, v;
for(int i = 0; i < Q; i++) {
// %s 它会读入一个不含空格、TAB和回车符的字符串，存入字符数组
// %c 会读入\n
scanf("%s%d%d", c, &l, &r);
if(c[0] == 'C') {
scanf("%d", &v);
add(0, l, v);
add(0, r + 1, -v);
add(1, l, l * v);
add(1, r + 1, -(r + 1) * v);
} else {
ll result = (sum[r] + (r + 1) * ask(0, r) - ask(1, r))
- (sum[l - 1] + l * ask(0, l - 1) - ask(1, l - 1));
printf("%lld\n", result);
}
}
}