fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  const int logn = 32, maxn = logn * 2e5 + 42;
  6. int cnt[maxn], to[maxn][2];
  7. int rt[maxn];
  8. int sz = 1;
  9.  
  10. void copy(int x)
  11.  {
  12.     to[sz][0] = to[x][0];
  13.     to[sz][1] = to[x][1];
  14.     cnt[sz] = cnt[x] + 1;
  15.  }
  16.  
  17. void upd(int v, unsigned n)
  18.  {
  19.     n ^= 1u << logn - 1;
  20.     v++;
  21.     copy(rt[v - 1]);
  22.     v = rt[v] = sz++;
  23.     for(int i = logn - 1; i >= 0; i--)
  24.     {
  25.         int c = (n >> i) & 1;
  26.         copy(to[v][c]);
  27.         v = to[v][c] = sz++;
  28.     }
  29.  }
  30.  
  31. unsigned find_by_order(int l, int r, int k)
  32.  {
  33.     l = rt[l];
  34.     r = rt[r];
  35.     unsigned ans = 0;
  36.     for(int i = logn - 1; i >= 0; i--)
  37.     {
  38.     	int c = 0;
  39.         if(cnt[to[r][0]] - cnt[to[l][0]] < k)
  40.         {
  41.             k -= cnt[to[r][0]] - cnt[to[l][0]];
  42.             ans |= 1u << i;
  43.             c = 1;
  44.         }
  45.         l = to[l][c];
  46.         r = to[r][c];
  47.     }
  48.     return ans;
  49.  }
  50.  
  51.  main()
  52.  {
  53.     ios::sync_with_stdio(0);
  54.     cin.tie(0);
  55.     int n, m;
  56.     cin >> n >> m;
  57.     int nw[n];
  58.     for(int i = 0; i < n; i++)
  59.         cin >> nw[i];
  60.     for(int i = 0; i < n; i++)
  61.         upd(i, nw[i]);
  62.     while(m--)
  63.     {
  64.         int l, r, k;
  65.         cin >> l >> r >> k;
  66.         cout << (int)(find_by_order(l - 1, r, k) ^ (1u << logn - 1)) << "\n";
  67.     }
  68.  }
  69.  
Runtime error #stdin #stdout 0s 103296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TphcLk
so online..
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!