【HDU】1166 敌兵布阵

 1 #include<cstdio>
 2 #include<cstring>
 3 #define MAXN 50010
 4 int tree[MAXN<<2];
 5 inline void PushUp(int rt)
 6 {
 7     tree[rt]=tree[rt<<1]+tree[rt<<1|1];
 8 }
 9 void Build(int L,int R,int rt)
10 {
11     if(L==R)
12         scanf("%d",&tree[rt]);
13     else
14     {
15         int mid=(L+R)>>1;
16         Build(L,mid,rt<<1);
17         Build(mid+1,R,rt<<1|1);
18         PushUp(rt);
19     }
20 }
21 void Update(int x,int val,int L,int R,int rt)
22 {
23     if(L==R)
24         tree[rt]+=val;
25     else
26     {
27         int mid=(L+R)>>1;
28         if(x<=mid)
29             Update(x,val,L,mid,rt<<1);
30         else
31             Update(x,val,mid+1,R,rt<<1|1);
32         PushUp(rt);
33     }
34 }
35 int Query(int x,int y,int L,int R,int rt)
36 {
37     if(x<=L&&R<=y)
38         return tree[rt];
39     int mid,ans;
40     mid=(L+R)>>1;
41     ans=0;
42     if(mid>=x)
43         ans+=Query(x,y,L,mid,rt<<1);
44     if(mid<y)
45         ans+=Query(x,y,mid+1,R,rt<<1|1);
46     return ans;
47 }
48 int main()
49 {
50     char cmd[10];
51     int c,n,x,y,ca=1;
52     scanf("%d",&c);
53     while(c--)
54     {
55         scanf("%d",&n);
56         Build(1,n,1);
57         printf("Case %d:\n",ca++);
58         while(scanf(" %s",cmd),strcmp(cmd,"End"))
59         {
60             scanf("%d%d",&x,&y);
61             if(!strcmp(cmd,"Add"))
62                 Update(x,y,1,n,1);
63             else if(!strcmp(cmd,"Sub"))
64                 Update(x,-y,1,n,1);
65             else
66                 printf("%d\n",Query(x,y,1,n,1));
67         }
68     }
69     return 0;
70 }
新博客：www.zhixiangli.com