hdu 1166 敌兵布阵

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define maxn 50010
  5 using namespace std;
  6 
  7 int a[maxn];
  8 struct node
  9 {
 10     int l,r;
 11     int sum;
 12 }tree[maxn*4];
 13 
 14 void build(int i,int l,int r)
 15 {
 16     tree[i].l=l;
 17     tree[i].r=r;
 18     if(l==r)
 19     {
 20         tree[i].sum=a[l];
 21         return ;
 22     }
 23     int mid=(l+r)>>1;
 24     build(i<<1,l,mid);
 25     build(i<<1|1,mid+1,r);
 26     tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
 27 }
 28 
 29 void add1(int i,int l,int r,int add)
 30 {
 31     if(tree[i].l==l&&tree[i].r==r)
 32     {
 33         tree[i].sum+=add;
 34         return ;
 35     }
 36     int mid=(tree[i].l+tree[i].r)>>1;
 37     if(r<=mid)
 38     {
 39         add1(i<<1,l,r,add);
 40     }
 41     else if(l>mid)
 42     {
 43         add1(i<<1|1,l,r,add);
 44     }
 45     else
 46     {
 47         add1(i<<1,l,mid,add);
 48         add1(i<<1|1,mid+1,r,add);
 49     }
 50     tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
 51 }
 52 
 53 int search1(int i,int l,int r)
 54 {
 55     if(tree[i].l==l&&tree[i].r==r)
 56     {
 57         return tree[i].sum;
 58     }
 59     int mid=(tree[i].l+tree[i].r)>>1;
 60     if(r<=mid)
 61     {
 62         return search1(i<<1,l,r);
 63     }
 64     else if(l>mid)
 65     {
 66         return search1(i<<1|1,l,r);
 67     }
 68     else
 69     {
 70         return (search1(i<<1,l,mid)+search1(i<<1|1,mid+1,r));
 71     }
 72 }
 73 
 74 int main()
 75 {
 76     int T,N,aa,bb;
 77     char s1[maxn];
 78     scanf("%d",&T);
 79     int case1=0;
 80     while(T--)
 81     {
 82         scanf("%d",&N);
 83         for(int i=1; i<=N; i++)
 84         {
 85             scanf("%d",&a[i]);
 86         }
 87         build(1,1,N);
 88         printf("Case %d:\n",++case1);
 89         while(1)
 90         {
 91             scanf("%s",s1);
 92             if(!strcmp(s1,"Add"))
 93             {
 94                 scanf("%d%d",&aa,&bb);
 95                 add1(1,aa,aa,bb);
 96             }
 97             else if(!strcmp(s1,"Query"))
 98             {
 99                 scanf("%d%d",&aa,&bb);
100                 printf("%d\n",search1(1,aa,bb));
101             }
102             else if(!strcmp(s1,"Sub"))
103             {
104                 scanf("%d%d",&aa,&bb);
105                 add1(1,aa,aa,-bb);
106             }
107             else if(!strcmp(s1,"End")) break;
108         }
109     }
110     return 0;
111 }