HDU 1166 敌兵布阵线段树区间求和更改-白红宇

HDU 1166 敌兵布阵线段树区间求和更改

阅读量：5240 次

发布时间：2019-06-14

本文共 1963 字，大约阅读时间需要 6 分钟。

水

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
             8 #include
             
               9 #include
              
                10 #include
               
                 11 #include
                
                  12 #include
                 
                   13 #include 
                  
                    14 using namespace std; 15 #define INF 0x3f3f3f3f 16 #define ll long long 17 #define clc(a,b) memset(a,b,sizeof(a)) 18 const int maxn=50000; 19 20 int ans; 21 struct node 22 { 23 int left,right,sum; 24 int mid() 25 { 26 return (left+right)>>1; 27 } 28 }tree[maxn*4]; 29 30 void build_tree(int l,int r,int o) 31 { 32 tree[o].left=l; 33 tree[o].right=r; 34 if(l==r) 35 { 36 scanf("%d",&tree[o].sum); 37 return ; 38 } 39 int mid=tree[o].mid(); 40 build_tree(l,mid,o<<1); 41 build_tree(mid+1,r,o<<1|1); 42 tree[o].sum=tree[o<<1].sum+tree[o<<1|1].sum; 43 } 44 45 void query(int l,int r,int o,int L,int R) 46 { 47 if(L<=l&&r<=R) 48 { 49 ans+=tree[o].sum; 50 return ; 51 } 52 int mid=tree[o].mid(); 53 if(R<=mid) 54 query(l,mid,o<<1,L,R); 55 else if(L>mid) 56 query(mid+1,r,o<<1|1,L,R); 57 else 58 { 59 query(l,mid,o<<1,L,R); 60 query(mid+1,r,o<<1|1,L,R); 61 } 62 } 63 64 void update(int l,int r,int o,int pos,int add) 65 { 66 if(l==r) 67 { 68 tree[o].sum+=add; 69 return ; 70 } 71 int mid=tree[o].mid(); 72 if(pos<=mid) 73 { 74 update(l,mid,o<<1,pos,add); 75 } 76 else 77 update(mid+1,r,o<<1|1,pos,add); 78 tree[o].sum=tree[o<<1].sum+tree[o<<1|1].sum; 79 } 80 81 int main() 82 { 83 int t,n,cnt; 84 int a,b; 85 char str[10]; 86 cnt=1; 87 scanf("%d",&t); 88 while(t--) 89 { 90 scanf("%d",&n); 91 build_tree(1,n,1); 92 printf("Case %d:\n",cnt++); 93 while(scanf("%s",str)) 94 { 95 if(str[0]=='E') 96 break; 97 scanf("%d%d",&a,&b); 98 if(str[0]=='Q') 99 {100 ans=0;101 query(1,n,1,a,b);102 printf("%d\n",ans);103 }104 else if(str[0]=='A')105 update(1,n,1,a,b);106 else107 update(1,n,1,a,-b);108 }109 }110 return 0;111 }