fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int t[600000], arr[600000], lazy[600000];
  4. int n, q;
  5.  
  6. void update(int ind, int lo, int hi, int i, int j)
  7. {
  8.     if(lazy[ind] == 1){
  9.         t[ind] = hi - lo + 1 - t[ind];
  10.         if(hi != lo){
  11.             lazy[2*ind + 1]^= 1;
  12.             lazy[2*ind]^= 1;
  13.         }
  14.         lazy[ind] = 0;
  15.     }
  16.     if (lo > hi || lo > j || hi < i)               
  17.         return;                 
  18.  
  19.     if (i <= lo && j >= hi)   {      
  20.         t[ind] = hi - lo + 1 - t[ind];
  21.         lazy[ind] = 0;
  22.         if(lo != hi){
  23.             lazy[2*ind]^= 1;
  24.             lazy[2*ind + 1]^= 1;
  25.         }
  26.         return;
  27.     }
  28.     int mid = (hi + lo) / 2;       
  29.  
  30.     update(2 * ind, lo, mid, i, j);
  31.     update(2 * ind + 1, mid + 1, hi, i, j);
  32.     t[ind] = t[ind*2] + t[ind*2 + 1];
  33. }
  34.  
  35.  int querySegTree(int ind, int lo, int hi, int i, int j)
  36. {
  37.  
  38.     if(lazy[ind] == 1){
  39.         t[ind] = hi - lo + 1 - t[ind];
  40.         if(lo != hi){
  41.             lazy[2*ind + 1]^= 1;
  42.             lazy[2*ind]^= 1;
  43.         }
  44.         lazy[ind] = 0;
  45.     }
  46.  
  47.            if (lo > j || hi < i)  {             
  48.         return 0;  
  49. }
  50.     if (i <= lo && j >= hi)   {      
  51.         return t[ind];
  52.     }
  53.     int mid = (hi + lo) / 2;       
  54.     if(i > mid){
  55.         return querySegTree(2 * ind + 1, mid + 1, hi, i, j);
  56.  
  57. }
  58. if(j <= mid){
  59.         return querySegTree(2 * ind, lo, mid, i, j);
  60. }
  61.     int leftQuery = querySegTree(2 * ind, lo, mid, i, j);
  62.     int rightQuery = querySegTree(2 * ind + 1, mid + 1, hi, i, j);
  63.  
  64.     return leftQuery + rightQuery;
  65. }
  66.  
  67. int main() {
  68.     cin>>n>>q;
  69.     for(int i = 1; i <= n; i++){
  70.         t[i] = 0;
  71.     }
  72.     while(q--){
  73.         int b, s, t;
  74.         cin>>b>>s>>t;
  75.         s++; t++;
  76.         if(b){
  77.             cout<<querySegTree(1, 1, n, s, t)<<'\n';
  78.         }
  79.         else{
  80.         update(1, 1, n, s, t);
  81.         }
  82.     }
  83.     return 0;
  84. }
Success #stdin #stdout 0s 4480KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/R1Kwkk
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!