fork download 
  1.     #include<iostream>
  2.     using namespace std;
  3.     const int MAX = 1e6;
  4.  
  5.     // here 0 means all tails up
  6.     int sgtree[3*MAX] = {0},LazyTree[3*MAX] = {0};
  7.  
  8.     //lazy query function
  9.     int LazyQuery(int stIndex,int b,int e,int qb,int qe){
  10.  
  11.         // NO OVERLAP
  12.         if(qb>e || qe<b)return 0;
  13.  
  14.         if(LazyTree[stIndex]==1){  //here one means Tree has pending Update
  15.             sgtree[stIndex] = (e-b+1) - sgtree[stIndex]; //new head = total length in interval - old head
  16.             if(b!=e){ //not a leaf node
  17.                 LazyTree[2*stIndex+1] = 1 - LazyTree[2*stIndex+1];
  18.                 LazyTree[2*stIndex+2] = 1 - LazyTree[2*stIndex+2];
  19.             }
  20.             LazyTree[stIndex] = 0;// putting it it previous form
  21.         }
  22.  
  23.         //TOTAL OVERLAP
  24.         if(qb<=b && qe>=e)return sgtree[stIndex];
  25.  
  26.         //PARTIAL OVERLAP
  27.         int x = LazyQuery(2*stIndex+1,b,(b+e)/2,qb,qe);
  28.         int y = LazyQuery(2*stIndex+2,(b+e)/2+1,e,qb,qe);
  29.         return x+y;
  30.     }
  31.  
  32.     void LazyUpdate(int stIndex,int b,int e,int qb,int qe){
  33.  
  34.         if(LazyTree[stIndex] == 1){ // taking care of old update
  35.             sgtree[stIndex] = (e-b+1) - sgtree[stIndex];
  36.  
  37.             if(b!=e){
  38.                 LazyTree[2*stIndex+1] = 1 - LazyTree[2*stIndex+1];
  39.                 LazyTree[2*stIndex+1] = 1 - LazyTree[2*stIndex+2];
  40.             }
  41.             LazyTree[stIndex] = 0;
  42.         }
  43.         // NO OVERLAP
  44.         if(qb>e || qe <b)return ;
  45.  
  46.         //TOTAL OVERLAP
  47.         if(b >= qb && e <= qe){
  48.             sgtree[stIndex] = (e-b+1)-sgtree[stIndex];
  49.             if(b!=e){
  50.                 LazyTree[2*stIndex+1] = 1 - LazyTree[2*stIndex+1];
  51.                 LazyTree[2*stIndex+2] = 1 - LazyTree[2*stIndex+2];
  52.             }
  53.             return;
  54.         }
  55.  
  56.         //PARTIAL OVERLAP
  57.         LazyUpdate(2*stIndex+1,b,(b+e)/2,qb,qe);
  58.         LazyUpdate(2*stIndex+2,((b+e)/2)+1,e,qb,qe);
  59.         sgtree[stIndex] = sgtree[2*stIndex+1] + sgtree[2*stIndex+2];
  60.     }
  61.  
  62.  
  63.  
  64.     int main(){
  65.         int n,q,x,y,i;
  66.         cin>>n>>q;
  67.         while(q--){
  68.             cin>>i;
  69.             if(i){
  70.                 cin>>x>>y;
  71.                 cout<<LazyQuery(0,0,n-1,x,y)<<endl;
  72.             }else{
  73.                 cin>>x>>y;
  74.                 LazyUpdate(0,0,n-1,x,y);
  75.             }
  76.  
  77.         }
  78.  
  79.     }
Success #stdin #stdout 0s 38672KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/9KZLpz
language:
C++14 (clang 8.0)
created:
8 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!