fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int logn = 20, maxn = logn << logn;
  6.  
  7. int root[maxn], to[maxn][2], cnt[maxn];
  8. int sz = 1, rt = 1;
  9.  
  10. void add(int x)
  11. {
  12.     int cur = root[rt] = sz++;
  13.     memcpy(to[cur], to[root[rt - 1]], sizeof(to[cur]));
  14.     cnt[cur] = cnt[root[rt - 1]];
  15.     rt++;
  16.     cnt[cur]++;
  17.     for(int i = logn - 1; i >= 0; i--)
  18.     {
  19.         bool c = x & (1 << i);
  20.         if(to[cur][c])
  21.         {
  22.             memcpy(to[sz], to[to[cur][c]], sizeof(to[sz]));
  23.             cnt[sz] = cnt[to[cur][c]];
  24.         }
  25.         cur = to[cur][c] = sz++;
  26.         cnt[cur]++;
  27.     }
  28. }
  29.  
  30. void remove(int k)
  31. {
  32.     rt -= k;
  33. }
  34.  
  35. int xor_max(int l, int r, int x)
  36. {
  37.     int a = root[l], b = root[r];
  38.     int y = 0;
  39.     for(int i = logn - 1; i >= 0; i--)
  40.     {
  41.         bool c = !(x & (1 << i));
  42.         if(cnt[to[a][c]] < cnt[to[b][c]])
  43.         {
  44.             y |= c << i;
  45.             a = to[a][c];
  46.             b = to[b][c];
  47.         }
  48.         else if(cnt[to[a][!c]] < cnt[to[b][!c]])
  49.         {
  50.             y |= (!c) << i;
  51.             a = to[a][!c];
  52.             b = to[b][!c];
  53.         }
  54.         else break;
  55.     }
  56.     return y;
  57. }
  58.  
  59. int order(int l, int r, int x)
  60. {
  61.     int a = root[l], b = root[r];
  62.     int ans = 0;
  63.     for(int i = logn - 1; i >= 0; i--)
  64.     {
  65.         bool c = x & (1 << i);
  66.         if(c) ans += cnt[to[b][0]] - cnt[to[a][0]];
  67.         a = to[a][c];
  68.         b = to[b][c];
  69.     }
  70.     ans += cnt[b] - cnt[a];
  71.     return ans;
  72. }
  73.  
  74. int kth_stat(int l, int r, int k)
  75. {
  76.     int a = root[l], b = root[r];
  77.     int ans = 0;
  78.     for(int i = logn - 1; i >= 0; i--)
  79.     {
  80.         if(k > cnt[to[b][0]] - cnt[to[a][0]])
  81.         {
  82.             k -= cnt[to[b][0]] - cnt[to[a][0]];
  83.             ans |= 1 << i;
  84.             a = to[a][1];
  85.             b = to[b][1];
  86.         }
  87.         else
  88.         {
  89.             a = to[a][0];
  90.             b = to[b][0];
  91.         }
  92.     }
  93.     return ans;
  94. }
  95.  
  96.  main()
  97.  {
  98.      //freopen("input.txt", "r", stdin);
  99.      ios::sync_with_stdio(0);
  100.      cin.tie(0);
  101.      int m;
  102.      cin >> m;
  103.      while(m--)
  104.      {
  105.          int type;
  106.          cin >> type;
  107.          if(type == 0)
  108.          {
  109.              int x;
  110.              cin >> x;
  111.              add(x);
  112.          }
  113.          else if(type == 1)
  114.          {
  115.              int l, r, x;
  116.              cin >> l >> r >> x;
  117.              cout << xor_max(l - 1, r, x) << "\n";
  118.          }
  119.          else if(type == 2)
  120.          {
  121.              int k;
  122.              cin >> k;
  123.              remove(k);
  124.          }
  125.          else if(type == 3)
  126.          {
  127.              int l, r, x;
  128.              cin >> l >> r >> x;
  129.              cout << order(l - 1, r, x) << "\n";
  130.          }
  131.          else
  132.          {
  133.              int l, r, k;
  134.              cin >> l >> r >> k;
  135.              cout << kth_stat(l - 1, r, k) << "\n";
  136.          }
  137.      }
  138.  }
Runtime error #stdin #stdout 0s 330944KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QI8sxL
Xor queries
language:
C++14 (gcc 8.3)
created:
9 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!