HDU 1166敌兵布阵

  1 #include <iostream>
  2 #include <cstdio>
  3 using namespace std;
  4 
  5 const int MaxSize=50001;
  6 
  7 int st[MaxSize*3];
  8 
  9 int num[MaxSize],N;
 10 
 11 void Build(int l,int r,int pos)
 12 {
 13     if(l==r)
 14     {
 15         st[pos]=num[l];
 16         return;
 17     }
 18 
 19     int mid=(l+r)>>1;
 20     Build(l,mid,pos*2);
 21     Build(mid+1,r,pos*2+1);
 22     st[pos]=st[pos*2]+st[pos*2+1];
 23 }
 24 
 25 void mod(int left,int right,int l,int r,int pos,int val)
 26 {
 27     if(left==right)
 28     {
 29         st[pos]+=val;
 30         return;
 31     }
 32     int mid=(left+right)>>1;
 33     if(r<=mid)
 34         mod(left,mid,l,r,pos*2,val);
 35     else if(l>mid)
 36         mod(mid+1,right,l,r,pos*2+1,val);
 37     else
 38     {
 39         mod(left,mid,l,mid,pos*2,val);
 40         mod(mid+1,right,mid+1,r,pos*2+1,val);
 41     }
 42     st[pos]=st[pos*2]+st[pos*2+1];
 43 }
 44 
 45 int Query(int left,int right,int l,int r,int pos)
 46 {
 47     if(l==left&&r==right)
 48         return st[pos];
 49 
 50     if(left==right)
 51         return st[pos];
 52 
 53     int mid=(left+right)>>1;
 54     if(r<=mid)
 55         return Query(left,mid,l,r,pos*2);
 56     else if(l>mid)
 57         return Query(mid+1,right,l,r,pos*2+1);
 58     else
 59     {
 60         int ln=Query(left,mid,l,mid,pos*2);
 61         int rn=Query(mid+1,right,mid+1,r,pos*2+1);
 62         return ln+rn;
 63     }
 64 }
 65 
 66 int main()
 67 {
 68     int T;
 69     scanf("%d",&T);
 70     for(int ks=1;ks<=T;ks++)
 71     {
 72         scanf("%d",&N);
 73         for(int i=1;i<=N;i++)
 74             scanf("%d",num+i);
 75         Build(1,N,1);
 76         char com[20];
 77         printf("Case %d:\n",ks);
 78         while(cin>>com)
 79         {
 80             if(com[0]=='E')
 81                 break;
 82             else if(com[0]=='Q')
 83             {
 84                 int l,r;
 85                 scanf("%d%d",&l,&r);
 86                 printf("%d\n",Query(1,N,l,r,1));
 87             }
 88             else if(com[0]=='A')
 89             {
 90                 int pos,val;
 91                 scanf("%d%d",&pos,&val);
 92                 mod(1,N,pos,pos,1,val);
 93             }
 94             else if(com[0]=='S')
 95             {
 96                 int pos,val;
 97                 scanf("%d%d",&pos,&val);
 98                 mod(1,N,pos,pos,1,-val);
 99             }
100         }
101     }
102     return 0;
103 }

posted on 2010-08-30 14:13 ZAKIR 阅读(181) 评论(0)  编辑 收藏 引用 所属分类: HDU


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿

随笔档案

文章分类

文章档案

大牛们

搜索

最新评论

阅读排行榜

评论排行榜