 # FLIPCOIN

a guest
Sep 2nd, 2014
1,082
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. // Stanisław Szcześniak code to FLIPCOIN
2. #include<cstdio>
3. #include<algorithm>
4. #include<vector>
5. #include<iostream>
6. #include<cmath>
7.
8. using namespace std;
9.
10. const int M = 1<<18;
11.
12. int heads_up[M<<1]; // it counts the number of heads-up coins in subtree, regardless of the operations made on it, and it parent,grandparent, grandgrandparent ...
13. int times[M<<1]; // it counts the parity of the number of flipping this subtree
14.
15. void add(int a, int b, int p, int k, int v)  { // flip coins on interval [a,b], [p,k] is actual interval, v is actual vertex
16.     if(k < a or p > b) // no intersction
17.         return; // if [p,k] has no intersection with [a,b], we end
18.     else if(a <= p && b >= k)  // [p,k] is in [a,b] so we can just change the parity of changes on this subtree
19.         times[v]^=1;
20.     else { // partial
21.         int sum = 0;
24.         if(times[v*2] == 0) // if left son has been flipped even times we add him to the result normally
26.         else // else we add the rest of the interval [p,k]
28.         if(times[v*2+1] == 0) // the same with right son
30.         else
33.     }
34. }
35.
36. int query(int a, int b, int p, int k, int v, int xsum) // a,b,p,k,v means the same, xsum is xor sum from 1 to v. We need this, because we keep heads_up regardless of what has happened to vertexes up v.
37. {
38.     if(k < a or p > b) // no intersction, result is zero
39.         return 0;
40.     else if(a <= p && b >= k) { // fully
41.         if((xsum^times[v]) == 0) // if v was flipped even times, return normally
43.         else // return rest of interval [p,k]
45.     }
46.     else { // partial
47.         int sum = 0; // partial intersection, so just walk down to left and right son
48.         sum += query(a,b,p,(p+k)/2,v*2,xsum^times[v]);
49.         sum += query(a,b,(p+k)/2+1,k,v*2+1,xsum^times[v]);
50.         return sum;
51.     }
52. }
53.
54.
55. int main () {
56.     int n,q,t,a,b;
57.     cin >> n >> q;
58.     while(q--) {
59.         cin >> t >> a >> b;
60.         if(t == 0)