比赛 |
线段数树状数组 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
数列操作C |
最终得分 |
100 |
用户昵称 |
忆轩 |
运行时间 |
5.539 s |
代码语言 |
C++ |
内存使用 |
9.47 MiB |
提交时间 |
2018-06-17 10:37:42 |
显示代码纯文本
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 100005
#define LL long long
using namespace std;
LL n, m, x, y, z;
string s;
struct nond {
int ll, rr;
LL sum, flag;
}tree[4*N];
void up(int now) {
tree[now].sum = tree[now*2].sum + tree[now*2+1].sum;
}
void down(int now) {
tree[now*2].flag += tree[now].flag;
tree[now*2+1].flag += tree[now].flag;
tree[now*2].sum += (tree[now*2].rr-tree[now*2].ll+1) * tree[now].flag;
tree[now*2+1].sum += (tree[now*2+1].rr-tree[now*2+1].ll+1) * tree[now].flag;
tree[now].flag = 0;
return ;
}
void build(int now, int l, int r) {
tree[now].ll = l; tree[now].rr = r;
tree[now].flag = 0;
if(l == r) {
scanf("%lld", &tree[now].sum);
return ;
}
int mid = (l+r) / 2;
build(now*2, l, mid);
build(now*2+1, mid+1, r);
up(now);
}
void change(int now, int l, int r) {
if(tree[now].ll==l && tree[now].rr==r) {
tree[now].flag += z;
tree[now].sum += (tree[now].rr-tree[now].ll+1) * z;
return ;
}
if(tree[now].flag) down(now);
int mid = (tree[now].ll+tree[now].rr) / 2;
if(l<=mid && mid<r) change(now*2, l, mid), change(now*2+1, mid+1, r);
else if(r<=mid) change(now*2, l, r);
else change(now*2+1, l, r);
up(now);
}
LL query(int now, int l, int r) {
if(tree[now].ll==l && tree[now].rr==r) return tree[now].sum;
if(tree[now].flag) down(now);
int mid = (tree[now].ll+tree[now].rr) / 2;
if(l<=mid && mid<r) return query(now*2, l, mid) + query(now*2+1, mid+1, r);
else if(r<=mid) return query(now*2, l, r);
else return query(now*2+1, l, r);
}
int main() {
freopen("shuliec.in","r",stdin);
freopen("shuliec.out","w",stdout);
scanf("%lld", &n);
build(1, 1, n);
scanf("%lld", &m);
for(int i = 1; i <= m; i++) {
cin >> s >> x >> y;
if(s[0] == 'A') { scanf("%lld", &z); change(1, x, y); }
else printf("%lld\n", query(1, x, y));
}
fclose(stdin); fclose(stdout);
return 0;
}