fork download 
  1. #include<bits/stdc++.h>
  2. #define TIME (1.0*clock()/CLOCKS_PER_SEC)
  3. #define pb push_back
  4. #define eb emplace_back
  5. #define id1 (id<<1)
  6. #define id2 (id<<1)|1
  7. #define ll long long
  8. #define ii pair<int,int>
  9. #define vi vector<int>
  10. #define vii vector<pair<int,int>>
  11. #define vl vector<long long>
  12. #define vll vector<pair<ll,ll>>
  13. #define li pair<long long,int>
  14. #define vil vector<pair<int,ll>>
  15. #define db double
  16. #define ff first
  17. #define ss second
  18. #define lb lower_bound
  19. #define ub upper_bound
  20. #define FOR(i,a,b) for(int i=(a);i<=(b);i++)
  21. #define F0R(i,a) FOR(i,0,a-1)
  22. #define ROF(i,a,b) for(int i=(b);i>=(a);i--)
  23. #define R0F(i,a) ROF(i,0,a-1)
  24. #define rep(a) F0R(_,a)
  25. #define each(a,x) for(auto&a:x)
  26. #define ALL(x) (x).begin(),(x).end()
  27. #define pq priority_queue<li,vector<li>,greater<li>>
  28. using namespace std;
  29. const int maxn=1e5+5;
  30.  
  31.  
  32. int q,totalxor=0;
  33. vector<array<int,2>> T;
  34. int cnt[40*maxn];
  35. int cnt0[40*maxn][22];
  36. int cnt1[40*maxn][22];
  37. int isEnd[40*maxn];
  38. ll pre[40*maxn];
  39.  
  40. void add(int x){
  41.     int val=x;
  42.     int root=0;
  43.     for(int i=21;i>=0;i--){
  44.         int bit=(val>>i)&1;
  45.         if(T[root][bit]==0){
  46.             T.emplace_back();
  47.             T[root][bit]=T.size()-1;
  48.         }
  49.         for(int j=21;j>=0;j--){
  50.             int xbit=(val>>j)&1;
  51.             if(xbit==0)cnt0[root][j]++;
  52.             else cnt1[root][j]++;
  53.         }
  54.         root=T[root][bit];
  55.         cnt[root]++;
  56.         pre[root]+=x;
  57.     }
  58.     isEnd[root]=x;
  59. }
  60.  
  61. void del(int x){
  62.     int val=x;
  63.     int root=0;
  64.     bool exists=true;
  65.     for(int i=21;i>=0;i--){
  66.         int bit=(val>>i)&1;
  67.         if(T[root][bit]==0||cnt[T[root][bit]]==0){
  68.             exists=false;
  69.             break;
  70.         }
  71.         root=T[root][bit];
  72.     }
  73.     if(!exists)return;
  74.  
  75.     root=0;
  76.     for(int i=21;i>=0;i--){
  77.         int bit=(val>>i)&1;
  78.         for(int j=21;j>=0;j--){
  79.             int xbit=(val>>j)&1;
  80.             if(xbit==0)cnt0[root][j]--;
  81.             else cnt1[root][j]--;
  82.         }
  83.         int preroot=root;
  84.         root=T[root][bit];
  85.         cnt[root]--;
  86.         pre[root]-=x;
  87.         if(cnt[root]==0){
  88.             T[preroot][bit]=0;
  89.         }
  90.     }
  91.     if(cnt[root]==0){
  92.         isEnd[root]=0;
  93.     }
  94. }
  95.  
  96. ll search(int k,int root,int i){
  97.     ll res=0;
  98.     if(k<=0)return 0;
  99.     if(k==cnt[root]){
  100.         for(int j=21;j>=0;j--){
  101.             if((totalxor>>j)&1){
  102.                 res+=cnt0[root][j]*(1LL<<j);
  103.             }
  104.             else{
  105.                 res+=cnt1[root][j]*(1LL<<j);
  106.             }
  107.         }
  108.         return res;
  109.     }
  110.    if (i == 0) {
  111.  
  112.         if (k > 0 && cnt[root] > 0) {
  113.  
  114.             return (isEnd[root] ^ totalxor) * k;
  115.         }
  116.         return 0;
  117.     }
  118.     if(i<0)return 0;
  119.  
  120.     if((totalxor>>i)&1){
  121.         if(T[root][0]&&k<=cnt[T[root][0]]){
  122.             return search(k,T[root][0],i-1);
  123.         }
  124.         else{
  125.             ll sum=0;
  126.             if(T[root][0]){
  127.                 sum=search(cnt[T[root][0]],T[root][0],i-1);
  128.             }
  129.             if(T[root][1]){
  130.                 sum+=search(k-(T[root][0]?cnt[T[root][0]]:0),T[root][1],i-1);
  131.             }
  132.             return sum;
  133.         }
  134.     }
  135.     else{
  136.         if(T[root][1]&&k<=cnt[T[root][1]]){
  137.             return search(k,T[root][1],i-1);
  138.         }
  139.         else{
  140.             ll sum=0;
  141.             if(T[root][1]){
  142.                 sum=search(cnt[T[root][1]],T[root][1],i-1);
  143.             }
  144.             if(T[root][0]){
  145.                 sum+=search(k-(T[root][1]?cnt[T[root][1]]:0),T[root][0],i-1);
  146.             }
  147.             return sum;
  148.         }
  149.     }
  150. }
  151.  
  152. void solve(){
  153.     T.emplace_back();
  154.     cin>>q;
  155.     while(q--){
  156.         int type;
  157.         cin>>type;
  158.         if(type==0){
  159.             int x;
  160.             cin>>x;
  161.             x^=totalxor;
  162.             add(x);
  163.         }
  164.         else if(type==1){
  165.             int x;
  166.             cin>>x;
  167.             x^=totalxor;
  168.             del(x);
  169.         }
  170.         else if(type==2){
  171.             int x;
  172.             cin>>x;
  173.             totalxor^=x;
  174.         }
  175.         else if(type==3){
  176.             int k;
  177.             cin>>k;
  178.             cout<<search(k,0,22)<<"\n";
  179.         }
  180.     }
  181. }
  182.  
  183. int main(){
  184.     ios_base::sync_with_stdio(false);
  185.     cin.tie(NULL);cout.tie(NULL);
  186.     //if(fopen("TASK.INP","r")){
  187.     //    freopen("TASK.INP","r",stdin);
  188.     //    freopen("TASK.OUT","w",stdout);
  189.     //}
  190.     int ntest=1;
  191.     //cin>>ntest;
  192.  
  193.     for(int i=1;i<=ntest;i++)solve();
  194.     cerr<<"\n"<<"Time elapsed "<<TIME<<"s.\n";
  195.     return 0;
  196. }
Success #stdin #stdout #stderr 0.01s 11948KB
comments (?)
stdin 
6
0 1
2 2
0 3
3 2
2 2
3 1
stdout 
6
1
stderr 
Time elapsed 0.005183s.
https://ideone.com/sCtLHw
language:
C++14 (gcc 8.3)
created:
7 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!