线段树板子题练手用
#include<cstdio>
using namespace std;
const int maxn=5e4+;
int a[maxn],n;
struct Node{
int l,r;
long long sum,lazy;
void update(long long val){
sum+=1ll*(r-l+)*val;
lazy+=val;
}
}tree[maxn*];
void push_up(int x){
tree[x].sum=tree[x<<].sum+tree[x<<|].sum;
}
void push_down(int x){
int lazyval=tree[x].lazy;
if(lazyval){
tree[x<<].update(lazyval);
tree[x<<|].update(lazyval);
tree[x].lazy=;
}
}
void build(int x,int l,int r){
tree[x].l=l,tree[x].r=r;
tree[x].sum=tree[x].lazy=;
if(l==r){
tree[x].sum=a[l];
}
else {
int mid=l+r>>;
build(x<<,l,mid);
build(x<<|,mid+,r);
push_up(x);
}
}
void update(int x,int l,int r,long long val){
int L=tree[x].l,R=tree[x].r;
if(L>=l&&R<=r){
tree[x].update(val);
}
else {
int mid=L+R>>;
push_down(x);
if(mid>=l)update(x<<,l,r,val);
if(mid<r)update(x<<|,l,r,val);
push_up(x);
}
}
long long query(int x,int l,int r){
int L=tree[x].l,R=tree[x].r;
if(L>=l&&R<=r){
return tree[x].sum;
}
else {
int mid=L+R>>;
long long ans=;
push_down(x);
if(mid>=l)ans+=query(x<<,l,r);
if(mid<r)ans+=query(x<<|,l,r);
push_up(x);
return ans;
}
}
int main(){
int t,kase=;
scanf("%d",&t);
while(t--){
int n;
printf("Case %d:\n",kase++);
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
build(,,n);
char op[];
while(scanf("%s",op)&&op[]!='E'){
if(op[]=='Q'){
int l,r;
scanf("%d%d",&l,&r);
printf("%lld\n",query(,l,r));
}
else if(op[]=='A'){
int l,r,c;
scanf("%d%d",&l,&c);
update(,l,l,c);
}
else {
int l,c;
scanf("%d%d",&l,&c);
update(,l,l,-c);
}
}
}
return ;
}