Hdu 1166 敌兵布阵

挺简单的线段树，单点更新。（貌似有人没用线段树也过了，不过效率略低）
做完后粘了别人的代码又去试了试，比我的快了50ms左右。
不过有些人把加减看做两个运算确实很浪费。一个Add解决了。
  1 #include<stdio.h>
  2 #define mid(a,b) ((a+b)>>1)
  3 const int N = 50008;
  4 
  5 struct campsite{
  6 
  7   int left, right;
  8   int sum;
  9 
 10 }army[4*N];
 11 
 12 void build(int root, int l, int r){
 13 
 14      army[root].left = l;
 15      army[root].right = r;
 16      army[root].sum = 0;
 17 
 18      if(l == r)
 19         return;
 20      build(root*2, l, mid(l, r));
 21      build(root*2 + 1, mid(l, r) + 1, r);
 22 }
 23 
 24 void minsert(int root, int pose, int value){
 25 
 26      if(army[root].left == pose && army[root].right == pose){
 27         army[root].sum += value;
 28         return;
 29      }
 30 
 31      army[root].sum += value;
 32 
 33      if(pose <= mid(army[root].left, army[root].right))
 34         minsert(root*2, pose, value);
 35      else
 36         minsert(root*2+1, pose, value);
 37 }
 38 
 39 void add(int root, int pose, int value){
 40 
 41     if(army[root].left == pose && army[root].right == pose){
 42         army[root].sum += value;
 43         return;
 44     }
 45 
 46     army[root].sum += value;
 47 
 48     if(pose <= mid(army[root].left, army[root].right))
 49         add(root*2, pose, value);
 50     else
 51         add(root*2+1, pose, value);
 52 }
 53 
 54 int query(int root, int l, int r){
 55 
 56     if(army[root].left == l && army[root].right == r)
 57         return army[root].sum;
 58 
 59     if(r <= mid(army[root].left, army[root].right))
 60         return query(root*2, l, r);
 61     else if(l > mid(army[root].left, army[root].right))
 62         return query(root*2+1, l, r);
 63     else{
 64         return query(root*2, l, mid(army[root].left, army[root].right))
 65                + query(root*2+1, mid(army[root].left, army[root].right) + 1, r);
 66     }
 67 
 68 }
 69 
 70 /*int main(){
 71 
 72   build(1, 1, 5);
 73   for(int i = 0; i < 15; i++)
 74     printf("%d %d
", army[i].left, army[i].right);
 75 
 76    return 0;
 77 
 78 }*/
 79 int main(){
 80 
 81    int t, nt, a, b;
 82    char op[10];
 83    scanf("%d", &t);
 84    nt = t;
 85 
 86    while(t --){
 87     int num, hei;
 88     scanf("%d",&num);
 89     build(1, 1, num);
 90     for(int i = 1; i <= num; i++){
 91         scanf("%d", &hei);
 92         minsert(1, i, hei);
 93     }
 94     int flag = 1;
 95     while(~scanf("%s", op)){
 96 
 97         if(op[0] == 'E')
 98             break;
 99         if(op[0] == 'A'){
100            scanf("%d %d", &a, &b);
101            add(1, a, b);
102         }
103         if(op[0] == 'S'){
104            scanf("%d %d", &a, &b);
105            add(1, a, -b);
106         }
107         if(op[0] == 'Q'){
108            scanf("%d %d", &a, &b);
109            if(flag){
110             printf("Case %d:
", nt - t);
111             flag = 0;
112            }
113            printf("%d
",query(1, a, b));
114         }
115 
116     }
117 
118    }
119 
120   return 0;
121 
122 }
View Code
Hdu 1166 敌兵布阵

相关推荐
