Advertisement
Guest User

FLIPCOIN

a guest
Sep 2nd, 2014
1,151
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.21 KB | None | 0 0
  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;
  22.         add(a,b,p,(p+k)/2,v*2);
  23.         add(a,b,(p+k)/2+1,k,v*2+1);
  24.         if(times[v*2] == 0) // if left son has been flipped even times we add him to the result normally
  25.             sum += heads_up[v*2];
  26.         else // else we add the rest of the interval [p,k]
  27.             sum += (k-p+1)/2-heads_up[v*2];
  28.         if(times[v*2+1] == 0) // the same with right son
  29.             sum += heads_up[v*2+1];
  30.         else
  31.             sum += (k-p+1)/2-heads_up[v*2+1];
  32.         heads_up[v] = sum;
  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
  42.             return heads_up[v];
  43.         else // return rest of interval [p,k]
  44.             return (k-p+1)-heads_up[v];
  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)
  61.             add(a,b,0,M-1,1);
  62.         else
  63.             cout << query(a,b,0,M-1,1,0) << endl;
  64.     }
  65. }
  66.  
  67. // That's it
  68. // If You don't understand something, just send me an email at stas.szczesniak@gmail.com
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement