fork download 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <set>
  6. #include <map>
  7. #include <stack>
  8. #include <queue>
  9. #include <cstring>
  10.  
  11. #define vi   vector<int>
  12. #define pb   push_back
  13. #define vvi  vector<vector<int> >
  14. #define pii  pair<int,int>
  15. #define ll   long long 
  16. #define vl   vector<ll>
  17. #define vvl  vector<vector<ll> > 
  18. #define mii  map<int,int> 
  19. #define msi  map<string,int> 
  20. #define vpii vector<pair<int,int> >
  21. #define mp   make_pair
  22. #define all(a)  a.begin(), a.end()
  23. #define inf 0x7fffffff
  24. #define lfc(a) 2*a+1
  25. #define rfc(a) 2*a+2
  26. #define s(i) scanf("%d",&i)
  27. using namespace std;
  28.  
  29. ll tree[200005];
  30. ll lazy[200005];
  31. void build_tree(ll *arr,int b,int e,int node)
  32. {
  33.     if(b==e)
  34.     {
  35.         tree[node]=arr[b];
  36.         return ;
  37.     }
  38.     int mid=(b+e)/2;
  39.     build_tree(arr,b,mid,2*node+1);
  40.     build_tree(arr,mid+1,e,2*node+2);
  41.     tree[node]=(tree[2*node+1]+tree[2*node+2]);
  42.  
  43. }
  44.  
  45. //increment range [i,j] by v
  46. void update_tree(ll *arr,int b,int e,int i,int j,int node)
  47. {
  48.     if(lazy[node]!=0)
  49.     {
  50.         tree[node]=((e-b+1)-tree[node]);//update it
  51.         if(b!=e)
  52.         {
  53.             //pushes the lazy to its child
  54.             lazy[lfc(node)]+=lazy[node];
  55.             lazy[lfc(node)]%=2;
  56.             lazy[rfc(node)]+=lazy[node];
  57.             lazy[rfc(node)]%=2;
  58.         }
  59.         lazy[node]=0;//reset lazy of node
  60.     }
  61.     if(e<i||b>j)
  62.     {
  63.         return ;
  64.  
  65.     }
  66.     if(b>=i&&e<=j)
  67.     {
  68.        tree[node]=((e-b+1)-tree[node]);
  69.         if(b!=e)
  70.         {
  71.             lazy[lfc(node)]+=1;
  72.             lazy[lfc(node)]%=2;
  73.             lazy[rfc(node)]+=1;
  74.             lazy[rfc(node)]%=2;
  75.         }
  76.         return ;
  77.     }
  78.     int mid=(b+e)/2;
  79.     update_tree(arr,b,mid,i,j,lfc(node));
  80.     update_tree(arr,mid+1,e,i,j,rfc(node));
  81.     tree[node]=(tree[lfc(node)]+tree[rfc(node)]);
  82.  
  83. }
  84.  
  85. ll query_tree(ll *arr,int b,int e,int i,int j,int node)
  86. {
  87.      if(lazy[node]!=0)
  88.     {
  89.         tree[node]=((e-b+1)-tree[node]);//update it
  90.         if(b!=e)
  91.         {
  92.             //pushes the lazy to its child
  93.             lazy[lfc(node)]+=lazy[node];
  94.             lazy[lfc(node)]%=2;
  95.             lazy[rfc(node)]+=lazy[node];
  96.             lazy[rfc(node)]%=2;
  97.         }
  98.         lazy[node]=0;//reset lazy of node
  99.     }
  100.     if(e<i||b>j)
  101.     {
  102.         return 0 ;
  103.  
  104.     }
  105.     if(b>=i&&e<=j)
  106.     {
  107.        return tree[node];
  108.  
  109.     }
  110.     int mid=(b+e)/2;
  111.     ll p1=query_tree(arr,b,mid,i,j,lfc(node));
  112.     ll p2=query_tree(arr,mid+1,e,i,j,rfc(node));
  113.     return (p1+p2);
  114.  
  115. }
  116. int main()
  117. {
  118.    // freopen("i.txt","r",stdin);
  119.     int n;
  120.     s(n);
  121.     ll arr[n];
  122.     memset(arr,0,8*n);
  123.     memset(lazy,0,sizeof(lazy));
  124.     memset(tree,0,sizeof(tree));
  125.     int e;
  126.     s(e);int a,b,c,d;
  127.     for (int i = 0; i < e; ++i)
  128.     {
  129.         s(a);
  130.         if(a==0)
  131.         {
  132.             s(b);s(c);
  133.             update_tree(arr,0,n-1,b-1,c-1,0);
  134.         }
  135.         else
  136.         {
  137.             s(b);s(c);
  138.             cout<<query_tree(arr,0,n-1,b-1,c-1,0)<<"\n";
  139.         }
  140.     }
  141.  
  142.  
  143.  
  144.  
  145.  
  146.  
  147.  
  148. }
  149.  
  150.  
Runtime error #stdin #stdout 0s 6224KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Hy49Dk
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!