fork download
copy 
  1. #include <iostream>
  2. #include<iomanip>
  3. #include <string>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <sstream>
  7. #include <queue>
  8. #include <deque>
  9. #include <iterator>
  10. #include <stack>
  11. #include <map>
  12. #include <set>
  13. #include <numeric>
  14. #include <limits>
  15. #include <math.h>
  16. #include <stdio.h>
  17. #include <string.h>
  18. #define MOD 1000000007
  19. #define EPS 1e-15
  20. #define ll long long
  21. #define ld long double
  22. #define pb push_back
  23. #define mp make_pair
  24. #define mt make_tuple
  25. #define F first
  26. #define S second
  27. #define endl '\n'
  28. #define FOREACH(it,x) for(__typeof__((x).begin()) it = (x).begin(); it != (x).end(); ++it)
  29. #define FOR(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);++i)
  30. #define ROF(i,a,b) for(ll i=(ll)(a);i>=(ll)(b);--i)
  31. const ld PI=3.141592653589793238L;
  32. const ll N=100005;
  33. using namespace std;
  34. //   <<>>
  35.  
  36. ll nb[(1<<15)+5]; // nb[i] how many occurences of i are there in our current query.We only insert every number once in the trie.
  37. ll a[N] , ans[50005];
  38. pair<pair<ll,ll>,pair<ll,ll> >qu[50005];
  39. ll block;
  40.  
  41. struct node{
  42.     struct node *z , *o;
  43.     ll n;
  44.     node(){
  45.         z=NULL;
  46.         o=NULL;
  47.         n=0;
  48.     }
  49. };
  50. node* root = new node();
  51.  
  52. void add(ll x){
  53.     ++nb[x];
  54.     if(nb[x] > 1) return;
  55.  
  56.     node* c = root;
  57.     ++c->n;
  58.     ROF(i,15,0){
  59.         if(x&(1<<i)){
  60.             if(c->o == NULL) c->o = new node();
  61.             c=c->o;
  62.         }else{
  63.             if(c->z == NULL) c->z = new node();
  64.             c=c->z;
  65.         }
  66.         ++c->n;
  67.     }
  68. }
  69.  
  70. void del(ll x){
  71.     --nb[x];
  72.     if(nb[x] > 0) return;
  73.  
  74.     node *c = root , *prv;
  75.     --c->n;
  76.     ROF(i,15,0){
  77.         prv = c;
  78.  
  79.         if(x&(1<<i)) c = c->o;
  80.         else c = c->z;
  81.  
  82.         --c->n;
  83.         if(c->n == 0){
  84.             if(x&(1<<i)) prv->o = NULL;
  85.             else prv->z = NULL;
  86.             return;
  87.         }
  88.     }
  89. }
  90.  
  91. ll query(ll x){
  92.     node* c = root;
  93.     ROF(i,15,0){
  94.         if(x&(1<<i)){
  95.             if(c->z != NULL) c=c->z;
  96.             else x-=(1<<i) , c=c->o;
  97.         }else{
  98.             if(c->o != NULL) x+=(1<<i) , c=c->o;
  99.             else  c=c->z;
  100.         }
  101.     }
  102.  
  103.     return x;
  104. }
  105.  
  106. bool cmp(pair<pair<ll,ll>,pair<ll,ll> >a,pair<pair<ll,ll>,pair<ll,ll> >b){
  107.     ll x = a.F.F / block , y = b.F.F / block;
  108.     if(x != y) return x < y;
  109.     return a.F.S < b.F.S;
  110. }
  111.  
  112. int main(){
  113.     ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  114.     //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
  115.  
  116.     ll tc; cin >> tc;
  117.     while(tc--){
  118.         FOR(i,0,1<<15) if(nb[i]) nb[i]=1 , del(i);
  119.  
  120.         ll n,q; cin >> n >> q;
  121.         FOR(i,1,n) cin >> a[i];
  122.         block = sqrt(n);
  123.  
  124.         FOR(i,1,q){
  125.             ll x,l,r; cin >> x >> l >> r;
  126.             qu[i] = mp(mp(l,r),mp(x,i));
  127.         }
  128.         sort(qu+1,qu+q+1,cmp);
  129.  
  130.         ll cl = qu[1].F.F , cr=qu[1].F.S;
  131.         FOR(i,cl,cr) add(a[i]);
  132.         ans[qu[1].S.S] = query(qu[1].S.F);
  133.  
  134.         FOR(i,2,q){
  135.             ll l = qu[i].F.F , r=qu[i].F.S;
  136.  
  137.             while(cl < l) del(a[cl]) , ++cl;
  138.             while(cl > l) --cl , add(a[cl]);
  139.             while(cr < r) ++cr , add(a[cr]);
  140.             while(cr > r) del(a[cr]) , --cr;
  141.  
  142.             ans[qu[i].S.S] = query(qu[i].S.F);
  143.         }
  144.  
  145.         FOR(i,1,q) cout << ans[i] << endl;
  146.     }
  147.  
  148.     return 0;
  149. }
  150.  
  151.  
Success #stdin #stdout 0s 4520KB
comments (?)
stdin
copy 
1
15 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
10 6 10
1023 7 7
33 5 8
182 5 10
181 1 13
5 10 15
99 8 9
33 10 14
stdout
copy 
13
1016
41
191
191
15
107
47
https://ideone.com/k5GnNn
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!