HDu 1166敵兵布陣(樹状配列)
10350 ワード
1 #include<stdio.h>
2 #include<string.h>
3 #define N 600000
4 int n;
5 int a[N],c[N];
6 int lowbit(int x)
7 {
8 return x&(-x);
9 }
10 int sum(int k)
11 {
12 int ans=0;
13 while(k>0)
14 {
15 ans+=c[k];
16 k=k-lowbit(k);
17 }
18 return ans;
19 }
20 int add(int pos ,int num)
21 {
22 while(pos<=n)
23 {
24 c[pos]+=num;
25 pos+=lowbit(pos);
26 }
27 }
28 int main()
29 {
30 int T,l,i;
31 scanf("%d",&T);
32 char str[10];
33 for(l=1;l<=T;l++)
34 {
35 scanf("%d",&n);
36 memset(c,0,sizeof(c));
37 a[0]=0;
38 for(i=1;i<=n;i++)
39 {
40 scanf("%d",&a[i]);
41 add(i,a[i]);
42
43 }
44 printf("Case %d:
",l);
45 while(scanf("%s",str)!=EOF)
46 {
47 if(strcmp(str,"End")==0)break;
48 if(strcmp(str,"Query")==0)
49 {
50 int x,y;
51 scanf("%d%d",&x,&y);
52 int t;
53 if(x>y)
54 {
55 t=x;x=y;y=t;
56 }
57 printf("%d
",sum(y)-sum(x-1));
58 }
59 else
60 {
61 int pos,y;
62 if(strcmp(str,"Add")==0)
63 {
64 scanf("%d%d",&pos,&y);
65 add(pos,y);
66
67 }
68 else
69 {
70 scanf("%d%d",&pos,&y);
71 add(pos,-y);
72
73 }
74
75 }
76 }
77
78 }
79 }