题目大意:
题解:
利用一个优先队列存储当前取到的数
然后再写一颗支持查找异或的k大值的Trie即可
由于同一个值\(x\)可能被\(a_i\text{ xor }a_j\)和\(a_j\text{ xor }a_i\)一起取到
所以只有在奇数次取值的时候再更新
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxn = 100010;
struct Node{
Node *ch[2];
int siz;
}*null,*root;
Node mem[maxn*33],*it;
inline void init(){
it = mem;null = it++;
null->ch[0] = null->ch[1] = null;
null->siz = 0;root = null;
}
inline Node* newNode(){
Node *p = it++;p->ch[0] = p->ch[1] = null;
p->siz = 0;return p;
}
void insert(int x){
Node *nw = root;nw->siz ++ ;
for(int i=30;i>=0;--i){
int id = (x>>i)&1;
if(nw->ch[id] == null) nw->ch[id] = newNode();
nw = nw->ch[id];nw->siz ++ ;
}
}
int kth(int x,int k){
int ret = 0;Node *nw = root;
for(int i=30;i>=0;--i){
int id = (x>>i)&1;
if(k <= nw->ch[id]->siz){
nw = nw->ch[id];
}else{
k -= nw->ch[id]->siz;
nw = nw->ch[id^1];
ret |= (1<<i);
}
}
return ret;
}
int a[maxn];
struct num{
int val,k,pos;
bool friend operator < (const num &a,const num &b){
return a.val > b.val;
}
num(const int &a,const int &b,const int &c){
val = a;k = b;pos = c;
}
};
priority_queue<num>q;
int main(){
init();root = newNode();
int n,k;read(n);read(k);
for(int i=1;i<=n;++i){
read(a[i]);
insert(a[i]);
}
for(int i=1;i<=n;++i){
q.push(num(kth(a[i],2),2,i));
}
int cnt = 0;k<<=1;
while(k--){
num tp = q.top();q.pop();
if((++cnt)&1) printf("%d ",tp.val);
if(tp.k == n) continue;
q.push(num(kth(a[tp.pos],tp.k+1),tp.k+1,tp.pos));
}
getchar();getchar();
return 0;
}