LightOJ - 1080 - Binary Simulation

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