3.敵兵布陣
C國的死對頭A國這段時間正在進行軍事演習(xí)肌稻，所以C國間諜頭子Derek和他手下Tidy又開始忙乎了。A國在海岸線沿
直線布置了N個工兵營地,Derek和Tidy的任務(wù)就是要監(jiān)視這些工兵營地的活動情況泡孩。由于采取了某種先進的監(jiān)測手段
，所以每個工兵營地的人數(shù)C國都掌握的一清二楚,每個工兵營地的人數(shù)都有可能發(fā)生變動寺谤，可能增加或減少若干人手,
但這些都逃不過C國的監(jiān)視仑鸥。 中央情報局要研究敵人究竟演習(xí)什么戰(zhàn)術(shù),所以Tidy要隨時向Derek匯報某一段連續(xù)的工
兵營地一共有多少人,例如Derek問:"Tidy,馬上匯報第3個營地到第10個營地共有多少人!"Tidy就要馬上開始計算這一段
的總?cè)藬?shù)并匯報。但敵兵營地的人數(shù)經(jīng)常變動变屁，而Derek每次詢問的段都不一樣眼俊，所以Tidy不得不每次都一個一個營
地的去數(shù)，很快就精疲力盡了粟关，Derek對Tidy的計算速度越來越不滿:"你個死肥仔疮胖，算得這么慢，我炒你魷魚!"Tidy想：
"你自己來算算看闷板，這可真是一項累人的工作!我恨不得你炒我魷魚呢!"無奈之下获列，Tidy只好打電話向計算機專家
Windbreaker求救,Windbreaker說："死肥仔，叫你平時做多點acm題和看多點算法書蛔垢，現(xiàn)在嘗到苦果了吧!"
Tidy說："我知錯了。迫悠。鹏漆。"但Windbreaker已經(jīng)掛掉電話了。Tidy很苦惱，這么算他真的會崩潰的艺玲，聰明的讀者括蝠，
你能寫個程序幫他完成這項工作嗎？不過如果你的程序效率不夠高的話饭聚，Tidy還是會受到Derek的責(zé)罵的.
輸入
第一行一個整數(shù)T忌警，表示有T組數(shù)據(jù)。
每組數(shù)據(jù)第一行一個正整數(shù)N（N<=50000）,
表示敵人有N個工兵營地秒梳，接下來有N個正整數(shù),第i個正整數(shù)ai代表第i個工兵營地里開始時有ai個人（1<=ai<=50）法绵。
接下來每行有一條命令，命令有4種形式：
(1) Add i j,i和j為正整數(shù),表示第i個營地增加j個人（j不超過30）
(2)Sub i j ,i和j為正整數(shù),表示第i個營地減少j個人（j不超過30）;
(3)Query i j ,i和j為正整數(shù),i<=j酪碘，表示詢問第i到第j個營地的總?cè)藬?shù);
(4)End 表示結(jié)束朋譬，這條命令在每組數(shù)據(jù)最后出現(xiàn);
每組數(shù)據(jù)最多有40000條命令
輸出
對第i組數(shù)據(jù),首先輸出“Case i:”和回車,
對于每個Query詢問，輸出一個整數(shù)并回車,表示詢問的段中的總?cè)藬?shù),這個數(shù)保持在int以內(nèi)
樣例輸入
1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End
樣例輸出
Case 1:
6
33
59
ac代碼
#include<cstdio>
#include<cstring>
#define maxl 50010
long long n,q;
long long a[maxl];
struct node {long long l,r,sum,tag;};
node tree[maxl<<2];
node zerot={0,0,0,0};
void build(long long k,long long l,long long r)
{
tree[k].l=l;tree[k].r=r;
if(l==r)
{
tree[k].sum=a[l];
return;
}
long long mid=(tree[k].l+tree[k].r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}
void prework()
{
scanf("%lld",&n);
for(long long i=1;i<=n;i++)
scanf("%lld",&a[i]);
build(1,1,n);
}
void change(long long k)
{
if(tree[k].l==tree[k].r)
tree[k].sum+=tree[k].tag;
else
{
tree[k].sum+=(tree[k].r-tree[k].l+1)*tree[k].tag;
tree[k<<1].tag+=tree[k].tag;
tree[k<<1|1].tag+=tree[k].tag;
}
tree[k].tag=0;
}
void padd(long long k,long long p,long long x){
if(p<tree[k].l||p>tree[k].r)return;
if(tree[k].l==tree[k].r)
{
tree[k].sum+=x;
return;
}
long long mid=(tree[k].l+tree[k].r)>>1;
if(p<=mid)
padd(k<<1,p,x);
else
if(p>mid)
padd(k<<1|1,p,x);
tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}
void add(long long k,long long l,long long r,long long x)
{
if(tree[k].tag)
change(k);
if(tree[k].l==l && tree[k].r==r)
{
tree[k].tag+=x;
return;
}
tree[k].sum+=(r-l+1)*x;
long long mid=(tree[k].l+tree[k].r)>>1;
if(r<=mid)
add(k<<1,l,r,x);
else
if(l>mid)
add(k<<1|1,l,r,x);
else
add(k<<1,l,mid,x),add(k<<1|1,mid+1,r,x);
}
long long query(long long k,long long l,long long r)
{
if(tree[k].tag)
change(k);
long long sum,mid=(tree[k].l+tree[k].r)>>1;
if(tree[k].l==l && tree[k].r==r)
return tree[k].sum;
if(r<=mid)
return query(k<<1,l,r);
else
if(l>mid)
return query(k<<1|1,l,r);
else
return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
}
void mainwork()
{
long long l,r,x;
char c[10];
//printf("%lld\n",q);
for(long long i=1;;i++)
{
scanf("%s",c);
if(c[0]=='E'){
break;
}
if(c[0]=='A')
{
scanf("%lld%lld",&l,&x);
padd(1,l,x);
}
if(c[0]=='S'){
scanf("%lld%lld",&l,&x);
padd(1,l,-1*x);
}
if(c[0]=='Q')
{
scanf("%lld%lld",&l,&r);
printf("%lld\n",query(1,l,r));
}
}
}
int main()
{
long long T;
scanf("%lld",&T);
for(long long i=1;i<=T;i++){
memset(tree,0,sizeof(tree));
prework();
printf("Case %lld:\n",i);
mainwork();
}
return 0;
}
