fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define LL long long
  4. #define ULL unsigned long long 
  5. LL tree[1000000+10],lazy[100000+10];
  6. void build(LL node,LL start,LL end)
  7. {
  8.     if(start==end)
  9.     {  tree[node] = 1;
  10.        return ;
  11.     }
  12.     LL mid = (start + end)/2;
  13.     build(2*node,start,mid);
  14.     build(2*node+1,mid+1,end);
  15.     tree[node] = tree[2*node] + tree[2*node+1];
  16. }
  17. void update(LL node,LL start,LL end,LL l,LL r)
  18. {   
  19.     if(lazy[node]!=0)
  20.     {   if(lazy[node]%2)
  21.         {  tree[node] = end-start+1 - tree[node] ;
  22.            if(start!=end)
  23.            {   lazy[node*2] = lazy[2*node] + lazy[node]; 
  24.                lazy[2*node+1] = lazy[2*node+1] + lazy[node];
  25.            } 
  26.            lazy[node] = 0;
  27.         }
  28.     }
  29.     if(start>end or end<l or start>r)
  30.       return ;
  31.     if(l<=start and end<=r)
  32.     {   
  33.         tree[node] = end-start+1 - tree[node] ;
  34.         if(start!=end)
  35.         {  lazy[2*node+1] = lazy[2*node+1] + 1;
  36.            lazy[2*node] = lazy[2*node] + 1;
  37.         }
  38.         return ;
  39.     }
  40.     LL mid = (start + end)/2;
  41.     update(2*node,start,mid,l,r);
  42.     update(2*node+1,mid+1,end,l,r);
  43.     tree[node] = tree[2*node] + tree[2*node+1] ;
  44. }
  45. LL query(LL node,LL start,LL end,LL l,LL r)
  46. {   if(start>end or start>r or end<l)
  47.      return 0;
  48.     if(lazy[node]!=0)
  49.     {  if(lazy[node]%2)
  50.         {  tree[node] = end-start+1 - tree[node] ;
  51.            if(start!=end)
  52.            {  lazy[2*node] = lazy[2*node] + lazy[node] ;
  53.               lazy[2*node+1]= lazy[node] + lazy[2*node+1];
  54.            }
  55.            lazy[node] = 0;
  56.         }
  57.     }
  58.     if(start>=l and end<=r)
  59.       return tree[node] ;
  60.     LL mid = (start + end)/2;
  61.     LL p1 = query(2*node,start,mid,l,r);
  62.     LL p2 = query(2*node+1,mid+1,end,l,r) ;
  63.     return (p1 + p2) ;
  64. }
  65. int main()
  66. {   ios_base::sync_with_stdio(false);
  67.     cin.tie(NULL);
  68.     LL n,q,d,l,r;
  69.     scanf("%lld%lld",&n,&q);
  70.     build(1,1,n) ;
  71.     while(q--)
  72.     {
  73.         scanf("%lld%lld%lld",&d,&l,&r);
  74.         if(d==0)
  75.         {  update(1,1,n,l,r);
  76.            /*for(LL i=1;i<=15;i++)
  77.              cout<<tree[i]<<" ";
  78.             cout<<endl;
  79.            for(LL i=1;i<=15;i++)
  80.              cout<<lazy[i]<<" " ;
  81.              cout<<endl;*/
  82.         }
  83.         else
  84.         { LL f_ans = query(1,1,n,l,r);
  85.           printf("%lld\n",r-l+1 - f_ans) ;
  86.         }
  87.  
  88.     }
  89. }
Success #stdin #stdout 0s 23832KB
comments (?)
stdin
copy 
4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4
stdout
copy 
1
2
https://ideone.com/hZku9U
language:
C++14 (gcc 8.3)
created:
6 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!