敌兵布阵

 1 #include <bits/stdc++.h>
 2 #define lid id<<1
 3 #define rid id<<1|1
 4 #define maxn 50005
 5 using namespace std;
 6 struct node
 7 {
 8     int l,r,num;
 9 }tr[maxn*4];
10 int s[maxn];
11 
12 void push_up(int id)
13 {
14     tr[id].num=tr[lid].num+tr[rid].num;
15 }
16 void build(int id,int l,int r)
17 {
18     tr[id].l=l;tr[id].r=r;
19     if(l==r)
20     {
21         tr[id].num=s[l];
22         return ;
23     }
24     int mid=(l+r)>>1;
25     build(lid,l,mid);
26     build(rid,mid+1,r);
27     push_up(id);
28 }
29 void update(int id,int l,int r,int add)
30 {
31     if(tr[id].l==l&&tr[id].r==r)
32     {
33         tr[id].num+=add;
34         return ;
35     }
36     int mid=(tr[id].l+tr[id].r)>>1;
37     if(l<=mid) update(lid,l,r,add);
38     else update(rid,l,r,add);
39     push_up(id);
40 }
41 int  query(int id,int l,int r)
42 {
43     if(tr[id].l>=l&&tr[id].r<=r)
44     {
45         return tr[id].num;
46     }
47     int mid=(tr[id].l+tr[id].r)>>1;
48     if(r<=mid) return query(lid,l,r);
49     else if(l>mid) return query(rid,l,r);
50     else return query(lid,l,mid)+query(rid,mid+1,r);
51 }
52 int main()
53 {
54     int t;
55     scanf("%d",&t);
56     int flag=0;
57     while(t--)
58     {
59         int n;
60         scanf("%d",&n);
61         for(int i=1;i<=n;i++) scanf("%d",&s[i]);
62         build(1,1,n);
63         char s[10];
64         printf("Case %d:\n",++flag);
65         while(~scanf("%s",s))
66         {
67             int l,r,add;
68             if(s[0]==‘E‘) break;
69             else if(s[0]==‘A‘)
70             {
71                 scanf("%d%d",&l,&add);
72                 update(1,l,l,add);
73             }
74             else if(s[0]==‘S‘)
75             {
76                 scanf("%d%d",&l,&add);
77                 update(1,l,l,-add);
78             }
79             else
80             {
81                 scanf("%d%d",&l,&r);
82                 int ans=query(1,l,r);
83                 printf("%d\n",ans);
84             }
85         }
86     }
87     return 0;
88 }