hdu1166敌兵布阵

题意：题目是中文的：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16216

分析：这道题目作为模板题其实值得多练习几次的。用树状数组来写：

View Code

 1 #include <stdio.h>
 2 #include <iostream>
 3 using namespace std;
 4 #define DEBUG
 5 const int MAXN = 50000 + 10;
 6 int a[MAXN], n;
 7 int lowbit(int x){return x&(-x);}
 8 int sum(int x){
 9     int ret=0;
10     while(x>0){
11         ret+=a[x];
12         x-=lowbit(x);
13     }
14     return ret;
15 }
16 void add(int x, int d){
17     while(x<=n){
18         a[x]+=d;
19         x+=lowbit(x);
20     }
21 }
22 int main(){
23 #ifndef DEBUG
24     freopen("in.txt", "r", stdin);
25 #endif
26     int T, cas=1;
27     scanf("%d", &T);
28     while(T--){
29         memset(a, 0, sizeof(a));
30         scanf("%d", &n);
31         int i, x;
32         for(i=1; i<=n; i++){
33             scanf("%d", &x);
34             add(i, x);
35         }
36         char cmd[10];
37         printf("Case %d:\n", cas++);
38         while(scanf("%s", cmd) && cmd[0]!='E'){
39             int a, b;
40             scanf("%d%d", &a, &b);
41             if(cmd[0]=='A') add(a, b);
42             else if(cmd[0]=='S') add(a, -b);
43             else if(cmd[0]=='Q') printf("%d\n", sum(b)-sum(a-1));
44         }
45     }
46     return 0;
47 }

 用线段树（点树）也是ok的：

View Code

 1 #include <stdio.h>
 2 #include <iostream>
 3 using namespace std;
 4 #define DEBUG
 5 const int MAXN = 50000 + 10;
 6 int data[MAXN], n;
 7 struct Node{
 8     int l, r, k;
 9 };
10 Node znode[4*MAXN];
11 int zfun(int a, int b){return a+b;}
12 void build(int l, int r, int n){
13     int mid=(l+r)>>1;
14     znode[n].l=l;
15     znode[n].r=r;
16     if(l==r) znode[n].k=data[l];
17     else{
18         build(l, mid, 2*n);
19         build(mid+1, r, 2*n+1);
20         znode[n].k=zfun(znode[2*n].k, znode[2*n+1].k);
21     }
22 }
23 int query(int l, int r, int n){
24     int mid=(znode[n].l+znode[n].r)>>1;
25     if(znode[n].l==l && znode[n].r==r) return znode[n].k;
26     else{
27         if(r<=mid) return query(l, r, 2*n);
28         else if(l>mid) return query(l, r, 2*n+1);
29         else return zfun(query(l, mid, 2*n), query(mid+1, r, 2*n+1));
30     }
31 }
32 void add(int nid, int d, int n){
33     int mid=(znode[n].l+znode[n].r)>>1;
34     if(znode[n].l==nid && znode[n].r==nid){
35         znode[n].k+=d;
36         int newn=n/2;
37         while(newn>=1){
38             znode[newn].k=zfun(znode[2*newn].k, znode[2*newn+1].k);
39             newn/=2;
40         }
41     }else{
42         if(nid<=mid) add(nid, d, 2*n);
43         else if(nid>mid) add(nid, d, 2*n+1);
44     }
45 }
46
47 int main(){
48 #ifndef DEBUG
49     freopen("in.txt", "r", stdin);
50 #endif
51     int T, cas=1;
52     scanf("%d", &T);
53     while(T--){
54         memset(data, 0, sizeof(data));
55         scanf("%d", &n);
56         int i, x;
57         for(i=1; i<=n; i++) scanf("%d", &data[i]);
58         build(1, n, 1);
59         char cmd[10];
60         printf("Case %d:\n", cas++);
61         while(scanf("%s", cmd) && cmd[0]!='E'){
62             int a, b;
63             scanf("%d%d", &a, &b);
64             if(cmd[0]=='A') add(a, b, 1);
65             else if(cmd[0]=='S') add(a, -b, 1);
66             else if(cmd[0]=='Q') printf("%d\n", query(a, b, 1));
67         }
68     }
69     return 0;
70 }