学步园

敌兵布阵

Time Limit: 2000/1000 MS
(Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4534    Accepted Submission(s): 1811

Problem Description

C
国的死对头A
国这段时间正在进行军事演习，所以C
国间谍头子Derek
和他手下Tidy
又开始忙乎了。A
国在海岸线沿直线布置了N
个工兵营 地,Derek
和Tidy
的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C
国都掌握的一清二楚,
每个工 兵营地的人数都有可能发生变动，可能增加或减少若干人手,
但这些都逃不过C
国的监视。

中央情报局要研究敌人究竟演习什么战术,
所以Tidy
要随时
向Derek
汇报某一段连续的工兵营地一共有多少人,
例如Derek
问:“Tidy,
马上汇报第3
个营地到第10
个营地共有多少人!”Tidy
就要马上开 始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而Derek
每次询问的段都不一样，所以Tidy
不得不每次都一个一个营地的去数，很快就精疲力
尽了，Derek
对Tidy
的计算速度越来越不满:"
你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy
想：“
你自己来算算看，这可真是一项累人的工作!
我 恨不得你炒我鱿鱼呢!”
无奈之下，Tidy
只好打电话向计算机专家Windbreaker
求救,Windbreaker
说：“
死肥仔，叫你平时做多点 acm
题和看多点算法书，现在尝到苦果了吧!”Tidy
说："
我知错了。。。"
但Windbreaker
已经挂掉电话了。Tidy
很苦恼，这么算他真的会 崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy
还是会受到Derek
的责骂的.

Input

第一行一个整数T
，表示有T
组数据。

每组数据第一行一个正整数N
（N<=50000
）,
表示敌人有N
个工兵营地，接下来有N
个正整数,
第i
个正整数ai
代表第i
个工兵营地里开始时有ai
个人（1<=ai<=50
）。

接下来每行有一条命令，命令有4
种形式：
(1) Add i j,i
和j
为正整数,
表示第i
个营地增加j
个人（j
不超过30
）
(2)Sub i j ,i
和j
为正整数,
表示第i
个营地减少j
个人（j
不超过30
）;
(3)Query i j ,i
和j
为正整数,i<=j
，表示询问第i
到第j
个营地的总人数;
(4)End
表示结束，这条命令在每组数据最后出现;

每组数据最多有40000
条命令

Output

对第i
组数据,
首先输出“Case i:”
和回车,

对于每个Query
询问，输出一个整数并回车,
表示询问的段中的总人数,
这个数最多不超过1000000
。

Sample Input

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

Sample Output

Case 1:

6

33

59

线段树入门练习题
.

代码如下
:

#include<stdio.h><br /> #include<string.h><br /> #define MAXN 50005<br /> struct ST<br /> {<br /> int l,r,sum;<br /> }stree[3*MAXN];<br /> void buildtree(int ll,int rr,int n)<br /> {<br /> stree[n].l=ll;<br /> stree[n].r=rr;<br /> stree[n].sum=0;<br /> int mid=(ll+rr)/2;<br /> if (ll==rr) return;<br /> buildtree(ll,mid,2*n);<br /> buildtree(mid+1,rr,2*n+1);<br /> }<br /> void insert(int ll,int rr,int a,int n)<br /> {<br /> stree[n].sum+=a;<br /> if (stree[n].l==stree[n].r) return;<br /> int mid=(stree[n].l+stree[n].r)/2;<br /> if (rr<=mid) insert(ll,rr,a,2*n);<br /> else<br /> if (ll>=mid+1) insert(ll,rr,a,2*n+1);<br /> }<br /> int count(int ll,int rr,int n)<br /> {<br /> int mid=(stree[n].l+stree[n].r)/2;<br /> if (ll==stree[n].l&&rr==stree[n].r) return stree[n].sum;<br /> else<br /> if (rr<=mid) return count(ll,rr,2*n);<br /> else<br /> if (ll>=mid+1) return count(ll,rr,2*n+1);<br /> else<br /> return count(ll,mid,2*n)+count(mid+1,rr,2*n+1);<br /> }<br /> int main()<br /> {<br /> int cas,i,a,n,m;<br /> char op[6];<br /> scanf("%d",&cas);<br /> for (int ca=1;ca<=cas;++ca)<br /> {<br /> scanf("%d",&n);<br /> buildtree(1,n,1);<br /> for (i=1;i<=n;++i)<br /> {<br /> scanf("%d",&a);<br /> insert(i,i,a,1);<br /> }<br /> printf("Case %d:/n",ca);<br /> while (scanf("%s",op)&&strcmp(op,"End"))<br /> {<br /> if (strcmp(op,"Add")==0)<br /> {<br /> scanf("%d%d",&m,&a);<br /> insert(m,m,a,1);<br /> }<br /> if (strcmp(op,"Sub")==0)<br /> {<br /> scanf("%d%d",&m,&a);<br /> insert(m,m,-a,1);<br /> }<br /> if (strcmp(op,"Query")==0)<br /> {<br /> scanf("%d%d",&m,&a);<br /> printf("%d/n",count(m,a,1));<br /> }<br /> }<br /> }<br /> return 0;<br /> }<br />