fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX_N = 1e5 + 5;
  5. const int BLOCK_SIZE = 505;
  6.  
  7. bool a[MAX_N];
  8. int cnt[2][MAX_N / BLOCK_SIZE + 5];
  9. int flip[MAX_N];
  10. int n;
  11.  
  12. void manualUpdate(int id, int l, int r){
  13.   int L = id * BLOCK_SIZE;
  14.   int R = (id + 1) * BLOCK_SIZE - 1;
  15.   R = min(R, n - 1);
  16.  
  17.   if(flip[id] & 1){
  18.     swap(cnt[0][id], cnt[1][id]);
  19.     for(int i = L; i <= R; i++)
  20.       a[i] = !a[i];
  21.   }
  22.  
  23.   flip[id] = 0;
  24.  
  25.   for(int i = l; i <= r; i++)
  26.     a[i] = !a[i];
  27.  
  28.   cnt[0][id] = cnt[1][id] = 0;
  29.   for(int i = L; i <= R; i++)
  30.     cnt[0][id] += !a[i],
  31.     cnt[1][id] += a[i];
  32. }
  33.  
  34. void blockUpdate(int lB, int rB){
  35.   for(int i = lB; i <= rB; i++)
  36.     flip[i]++;
  37. }
  38.  
  39. int main(){
  40.   ios_base::sync_with_stdio(0);
  41.   cin.tie(0);
  42.   cout.tie(0);
  43.  
  44.   int m;
  45.   cin >> n >> m;
  46.  
  47.   for(int i = 0; i < n; i++)
  48.     cnt[0][i / BLOCK_SIZE]++;
  49.  
  50.   while(m--){
  51.     int query;
  52.     cin >> query;
  53.  
  54.     if(query == 0){
  55.       int l, r;
  56.       cin >> l >> r;
  57.       --l, --r;
  58.  
  59.       int blockL = l / BLOCK_SIZE;
  60.       int blockR = r / BLOCK_SIZE;
  61.  
  62.       // assert(blockL == blockR);
  63.  
  64.       if(blockL == blockR)
  65.         manualUpdate(blockL, l, r);
  66.       else{
  67.         blockUpdate(blockL + 1, blockR - 1);
  68.         manualUpdate(blockL, l, (blockL + 1) * BLOCK_SIZE - 1);
  69.         manualUpdate(blockR, blockR * BLOCK_SIZE, r);
  70.       }
  71.     }
  72.  
  73.     else{
  74.       int l, r;
  75.       cin >> l >> r;
  76.       --l, --r;
  77.  
  78.       int blockL = l / BLOCK_SIZE;
  79.       int blockR = r / BLOCK_SIZE;
  80.       int ans = 0;
  81.  
  82.       // assert(blockL == blockR);
  83.  
  84.       if(blockL == blockR){
  85.         for(int i = l; i <= r; i++)
  86.           ans += (flip[blockL] & 1 ? !a[i] : a[i]);
  87.  
  88.         cout << ans << '\n';
  89.         continue;
  90.       }
  91.  
  92.       for(int i = blockL + 1; i <= blockR - 1; i++)
  93.         ans += (flip[i] & 1 ? cnt[0][i] : cnt[1][i]);
  94.       for(int i = l, endP = (blockL + 1) * BLOCK_SIZE - 1; i <= endP; i++)
  95.         ans += (flip[blockL] & 1 ? !a[i] : a[i]);
  96.       for(int i = blockR * BLOCK_SIZE; i <= r; i++)
  97.         ans += (flip[blockR] & 1 ? !a[i] : a[i]);
  98.       cout << ans << '\n';
  99.     }
  100.   }
  101.  
  102.   return 0;
  103. }
Runtime error #stdin #stdout 0.01s 5464KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/iSBefk
language:
C++14 (gcc 8.3)
created:
2 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!