LightOJ - 1112 - Curious Robin Hood

1. #include <bits/stdc++.h>
2. #define C 100003
3. using namespace std;
4.  
5. int Sack[C], Tree[C*3];
6.  
7. void build(int b, int e, int node){
8.     if(b >= e){
9.         if(b == e)Tree[node] = Sack[b];
10.         return;
11.     }
12.     int mid = (b+e) >> 1, internal1 = (node << 1), internal2 = internal1+1;
13.     build(b, mid, internal1);
14.     build(mid+1, e, internal2);
15.     Tree[node] = Tree[internal1] + Tree[internal2];
16. }
17.  
18. void update(int b, int e, int node, int I){
19.     if(b > I || e < I)return;
20.     if(b >= e){
21.         if(b == e)Tree[node] = Sack[b];
22.         return;
23.     }
24.     int mid = (b+e) >> 1, internal1 = (node << 1), internal2 = internal1+1;
25.     update(b, mid, internal1, I);
26.     update(mid+1, e, internal2, I);
27.     Tree[node] = Tree[internal1] + Tree[internal2];
28. }
29.  
30. int query(int b, int e, int node, int I, int J){
31.     if(b >= I && e <= J)return Tree[node];
32.     if(b > J || e < I)return 0;
33.     if(b > e)return 0;
34.     int mid = (b+e) >> 1, internal1 = (node << 1), internal2 = internal1+1;
35.     int x = query(b, mid, internal1, I, J);
36.     int y = query(mid+1, e, internal2, I, J);
37.     return x+y;
38. }
39.  
40. int main(){
41.     int T, I, J, V, N, Q, F, CS = 0;
42.     scanf("%d", &T);
43.     while(T--){
44.         scanf("%d %d", &N, &Q);
45.         for(int i = 0; i < N; i++)scanf("%d", &Sack[i]);
46.         memset(Tree, 0, sizeof(Tree));
47.         build(0, N-1, 1);
48.         printf("Case %d:\n", ++CS);
49.         for(int i = 1; i <= Q; i++){
50.             scanf("%d", &F);
51.             if(F == 1){
52.                 scanf("%d", &I);
53.                 printf("%d\n", Sack[I]);
54.                 Sack[I] = 0;
55.                 update(0, N-1, 1, I);
56.             }
57.             if(F == 2){
58.                 scanf("%d %d", &I, &V);
59.                 Sack[I] += V;
60.                 update(0, N-1, 1, I);
61.             }
62.             if(F == 3){
63.                 scanf("%d %d", &I, &J);
64.                 printf("%d\n", query(0, N-1, 1, I, J));
65.             }
66.         }
67.     }
68.     return 0;
69. }