# flipcoinerror

a guest
Jan 27th, 2015
180
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <algorithm>
3. using namespace std;
4. #include<string.h>
5. #include<stdlib.h>
6. #include<math.h>
7. #include<stdio.h>
8. #include<cmath>
9. #define MAX (1<<17+5)
10. long long int tree[6*1000000];
11. long long int lazy[6*1000000];
12.
13. void update_tree(long long int node,long long   int a,long long  int b,long long  int i,long long  int j) {
14.
15.     if(lazy[node] == 1) { // This node needs to be updated
16.       tree[node] = abs( (b-a+1) - tree[node]); // Update it // ***** absolute is vimp
17.
18.         if(a != b) {
19.             lazy[node*2] = 1-lazy[node*2]; // Mark child as lazy
20.             lazy[node*2+1] = 1-lazy[node*2+1]; // Mark child as lazy
21.         }
22.
23.         lazy[node] = 0; // Reset it
24.     }
25.
26.     if(a > b || a > j || b < i) // Current segment is not within range [i, j]
27.         return;
28.
29.     if(a >= i && b <= j) { // Segment is fully within range
30.              tree[node] = abs((b-a+1) - tree[node]); // Update it // ***** absolute is vimp
31.
32.         if(a != b) { // Not leaf node
33.             lazy[node*2] = 1;
34.             lazy[node*2+1] = 1;
35.         }
36.
37.             return;
38.     }
39.
40.     update_tree(node*2, a, (a+b)/2, i, j); // Updating left child
41.     update_tree(1+node*2, 1+(a+b)/2, b, i, j); // Updating right child
42.
43.     tree[node] = tree[node*2] + tree[node*2+1]; // Updating root with max value
44. }
45.
46. long long int query_tree(long long  int node,long long  int a,long long  int b,long long  int i,long long  int j) {
47.
48.     if(lazy[node] == 1) { // This node needs to be updated
49.
50.         tree[node] = abs((b-a+1) - tree[node]); // Update it
51.
52.         if(a != b) {
53.             lazy[node*2] = 1-lazy[node*2]; // Mark child as lazy
54.             lazy[node*2+1] = 1-lazy[node*2+1]; // Mark child as lazy
55.         }
56.
57.         lazy[node] = 0; // Reset it
58.     }
59.
60.     if(a > b || a > j || b < i) return 0; // Out of range
61.     if(a >= i && b <= j) // Current segment is totally within range [i, j]
62.         return tree[node];
63.
64.     long long int q1= 0 ;
65.     q1 = query_tree(node*2, a, (a+b)/2, i, j); // Query left child
66.     long long int q2 =0 ;
67.     q2 = query_tree(1+node*2, 1+(a+b)/2, b, i, j); // Query right child
68.
69.     long long int res = q1 + q2; // Return final result
70.
71.     return res;
72. }
73.
74. int main() {
75.   long long  int N,Q ;
76.   long long  int a,b,c ;
77.
78.
79.   //for(int i = 0; i < N; i++) arr[i] = 0;
80.
81.   memset(tree,0,sizeof(tree));
82.   memset(lazy,0,sizeof(lazy));
83.
84.   scanf("%lld %lld",&N, &Q) ;
85.
86.   for (long long int i=0; i < Q; i++) {
87.     scanf("%lld %lld %lld",&a,&b,&c);
88.
89.     if (a==1)
90.       {
91.         printf("%lld\n",query_tree(1, 0, N-1, b, c)) ;
92.       }
93.     else if (a==0)
94.       {
95.         update_tree(1, 0, N-1, b, c);
96.       }
97.   }
98.   return 0;
99. }
RAW Paste Data