fork(1) download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int n,m;
  6.  
  7. struct tree
  8. {
  9.     int flag,sum;
  10. };
  11. tree seg[500000];
  12. int lazy[500000]={0};
  13.  
  14. void build_tree(int pos,int low,int high)
  15. {
  16.     if(low==high)
  17.     {
  18.         seg[pos].flag=seg[pos].sum=0;
  19.         return;
  20.     }
  21.     int mid=(low+high)/2;
  22.     build_tree(2*pos+1,low,mid);
  23.     build_tree(2*pos+2,mid+1,high);
  24.     seg[pos].flag=seg[pos].sum=0;
  25. }
  26. void update(int pos,int low,int high,int l,int r)
  27. {
  28.  
  29.     if(lazy[pos]!=0)
  30.     {
  31.         seg[pos].flag^=1;
  32.         if(lazy[pos]%2==1)
  33.             seg[pos].sum=(high-low+1)-seg[pos].sum;
  34.         if(low!=high)
  35.         {
  36.             lazy[2*pos+1]++;
  37.             lazy[2*pos+2]++;
  38.         }
  39.         lazy[pos]=0;
  40.     }
  41.  
  42.  
  43.     if(low>r||high<l)
  44.         return;
  45.  
  46.     if(low>=l&&high<=r)
  47.     {
  48.         seg[pos].flag^=1;
  49.         seg[pos].sum=(high-low+1)-seg[pos].sum;
  50.         if(low!=high)
  51.         {
  52.             lazy[2*pos+1]++;
  53.             lazy[2*pos+2]++;
  54.         }
  55.         return;
  56.     }
  57.  
  58.     int mid=(low+high)/2;
  59.     update(2*pos+1,low,mid,l,r);
  60.     update(2*pos+2,mid+1,high,l,r);
  61.     seg[pos].flag=seg[2*pos+1].flag||seg[2*pos+2].flag;
  62.     seg[pos].sum=seg[2*pos+1].sum+seg[2*pos+2].sum;
  63. }
  64.  
  65. int query(int pos,int low,int high,int l,int r)
  66. {
  67.     if(low>r||high<l)
  68.         return 0;
  69.     if(lazy[pos]!=0)
  70.     {
  71.         seg[pos].flag^=1;
  72.         if(lazy[pos]%2==1)
  73.             seg[pos].sum=(high-low+1)-seg[pos].sum;
  74.         if(low!=high)
  75.         {
  76.             lazy[2*pos+1]++;
  77.             lazy[2*pos+2]++;
  78.         }
  79.         lazy[pos]=0;
  80.     }
  81.     if(low>=l&&high<=r)
  82.         return(seg[pos].sum);
  83.     int mid=(low+high)/2;
  84.     int p1=query(2*pos+1,low,mid,l,r);
  85.     int p2=query(2*pos+2,mid+1,high,l,r);
  86.     return (p1+p2);
  87. }
  88. int main()
  89. {
  90.  
  91.    cin>>n>>m;
  92.    int x,y,z;
  93.    build_tree(0,0,n-1);
  94.    while(m--)
  95.    {
  96.         cin>>x>>y>>z;
  97.         if(x==0)
  98.         {
  99.             update(0,0,n-1,y-1,z-1);
  100.         }
  101.         else
  102.         {
  103.             cout<<query(0,0,n-1,y-1,z-1)<<endl;
  104.         }
  105.    }
  106. }
Success #stdin #stdout 0s 21096KB
comments (?)
stdin
copy 
4 4 
0 1 4
 0 3 4 
1 3 3 
1 4 4
stdout
copy 
0
0
https://ideone.com/hMyU7P
language:
C++14 (clang 8.0)
created:
7 years ago
visibility:
secret

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!