SHARE
TWEET

Untitled

Shiam7777777 Mar 20th, 2019 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  4. #define ll long long
  5. #define ld double
  6. #define llu long long unsigned
  7.  
  8. #define mx 3000001
  9.  
  10. int arr[ mx ];
  11.  
  12. struct info {
  13.     int prop, sum0 , sum1;
  14. } tree[mx * 3];
  15.  
  16. void init(int node, int b, int e)
  17. {
  18.     if (b == e) {
  19.         tree[node].sum0 = 1;
  20.         tree[node].sum1 = 0;
  21.         return;
  22.     }
  23.     int Left = node << 1;
  24.     int Right = ( node << 1 ) + 1;
  25.     int mid = (b + e) >> 1;
  26.     init(Left, b, mid);
  27.     init(Right, mid + 1, e);
  28.     tree[node].sum0 = tree[Left].sum0 + tree[Right].sum0;
  29.     tree[node].sum1 = tree[Left].sum1 + tree[Right].sum1;
  30. }
  31.  
  32. void update(int node, int b, int e, int i, int j, int x)
  33. {
  34.     if (i > e || j < b)
  35.         return;
  36.     if (b >= i && e <= j)
  37.     {
  38.         swap( tree[node].sum0 , tree[node].sum1 );
  39. //        tree[node].sum += ((e - b + 1) * x);    //  adding sum
  40.         tree[node].prop += x;
  41.         return;
  42.     }
  43.     int Left = node << 1;
  44.     int Right = (node << 1) + 1;
  45.     int mid = (b + e) >> 1;
  46.     update(Left, b, mid, i, j, x);
  47.     update(Right, mid + 1, e, i, j, x);
  48.     tree[node].sum0 = tree[Left].sum0 + tree[Right].sum0;
  49.     tree[node].sum1 = tree[Left].sum1 + tree[Right].sum1;
  50.     int rot = tree[node].prop % 2;
  51.     if( rot )
  52.     {
  53.         swap( tree[node].sum0 , tree[node].sum1 );
  54.     }
  55. }
  56.  
  57. info query(int node, int b, int e, int i, int j, int carry = 0)
  58. {
  59.     if (i > e || j < b)
  60.     {
  61.         info tmp;
  62.         tmp.prop = 0;
  63.         tmp.sum0 = 0;
  64.         tmp.sum1 = 0;
  65.         return tmp;
  66.     }
  67.  
  68.  
  69.     if (b >= i and e <= j)
  70.     {
  71.         info tr;
  72.         tr = tree[node];
  73.         int rot = carry % 2;
  74.         if( rot )
  75.         {
  76.             swap( tr.sum0 , tr.sum1 );
  77.         }
  78.         return tr;
  79. //        return tree[node].sum + carry * (e - b + 1);
  80.     }
  81.  
  82.     int Left = node << 1;
  83.     int Right = (node << 1) + 1;
  84.     int mid = (b + e) >> 1;
  85.  
  86.     info p1 = query(Left, b, mid, i, j, carry + tree[node].prop);
  87.     info p2 = query(Right, mid + 1, e, i, j, carry + tree[node].prop);
  88.  
  89.     info tmp;
  90.     tmp.sum0 = p1.sum0 + p2.sum0;
  91.     tmp.sum1 = p1.sum1 + p2.sum1;
  92.     tmp.prop = 0;
  93.     return tmp;
  94. //    return p1 + p2;
  95. }
  96.  
  97. int main()
  98. {
  99.     fast;
  100.     int n , q;
  101.     cin>>n>>q;
  102.     init( 1 , 1 , n );
  103.     while( q-- )
  104.     {
  105.         int t;
  106.         cin>>t;
  107.         if( t == 0 )
  108.         {
  109.             int i , j;
  110.             cin>>i>>j;
  111.             update( 1 , 1 , n , i+1 , j+1 , 1 );
  112.         }
  113.         else if( t == 1 )
  114.         {
  115.             int i , j;
  116.             cin>>i>>j;
  117.             info tmp;
  118.             tmp = query( 1 , 1 , n , i+1 , j+1 );
  119.             cout<<tmp.sum1<<endl;
  120.         }
  121.     }
  122.     return 0;
  123. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top