fork download
copy 
  1. //Y. Tấn và phép XOR
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5. #define For(i, a, b) for(int i = a; i <= b; ++i)
  6. #define Forn(i, b, a) for(int i = b; i >= a; --i)
  7. #define endl '\n'
  8. #define fi first
  9. #define se second
  10. const int maxn = 1e6 + 5;
  11. const int lim = (1 << 20) - 1;
  12. int st[maxn * 4], n, q, a[maxn], ans[maxn];
  13. vector<ll> s;
  14. struct Query
  15. {
  16.     int l, id;
  17.     ll k;
  18. };
  19. vector<Query> qr[maxn];
  20. void update(int id, int l, int r, int pos, int val)
  21. {
  22.     if(l > pos || r < pos) return;
  23.     if(l == r)
  24.     {
  25.         st[id] = max(st[id], val);
  26.         return;
  27.     }
  28.     int mid = (r + l) >> 1;
  29.     update(id << 1, l, mid, pos, val);
  30.     update(id << 1 | 1, mid + 1, r, pos, val);
  31.     st[id] = max(st[id << 1], st[id << 1 | 1]);
  32. }
  33.  
  34. int query(int x, int l)
  35. {
  36.     int u = 1, ans = 0;
  37.     for(int i = 19; i >= 0; i--)
  38.     {
  39.         int bit = (x >> i) & 1;
  40.         int L = u << 1 | (bit ^ 1);
  41.         int R = u << 1 | bit;
  42.         if(st[L] >= l)
  43.         {
  44.             ans |= (1 << i);
  45.             u = L;
  46.         } else u = R;
  47.     }
  48.     return ans;
  49. }
  50. signed main()
  51. {
  52.     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  53.     cin >> n;
  54.     For(i, 1, n) cin >> a[i];
  55.     cin >> q;
  56.     For(i, 1, q)
  57.     {
  58.         int l, r, k;
  59.         cin >> l >> r >> k;
  60.         qr[r].push_back({l, i, k});
  61.     }
  62.     int l = 1;
  63.     For(i, 1, n) if(!qr[i].empty())
  64.     {
  65.         while(l <= i)
  66.         {
  67.             update(1, 0, lim, a[l], l);
  68.             l++;
  69.         }
  70.         for(Query it: qr[i]) ans[it.id] = query(it.k, it.l);
  71.     }
  72.     For(i, 1, q) cout << ans[i] << endl;
  73.  
  74.     return 0;
  75. }
  76.  
  77.  
Success #stdin #stdout 0.01s 28072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/d9tLyB
language:
C++14 (gcc 8.3)
created:
2 days 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!