做这题要知道一个技巧是可以用Trie树来查找与一个数异或第K大/小的数字.
套一个堆,这题就做完了.
1 #include2 #include 3 #include 4 using namespace std; 5 #define ll long long 6 #define FILE "dealing" 7 #define up(i,j,n) for(int i=j;i<=n;i++) 8 #define db long double 9 #define pii pair 10 #define pb push_back11 #define mem(a,L) memset(a,0,sizeof(int)*(L+1))12 template inline bool cmin(T& a,T b){ return a>b?a=b,true:false;}13 template inline bool cmax(T& a,T b){ return a inline T squ(T a){ return a*a;}15 const ll maxn=2000100+10,inf=1e9+10,limit=1e7;16 int read(){17 int x=0,f=1,ch=getchar();18 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();}19 while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();20 return x*f;21 }22 int n,K,a[maxn];23 int cnt,c[maxn][2],fa[maxn],siz[maxn],rt;24 void updata(int o){siz[o]=siz[c[o][0]]+siz[c[o][1]];}25 void add(int& o,int x,int dep){26 if(!o)o=++cnt;27 if(dep==-1){28 siz[o]++;29 return;30 }31 if(x&(1< =k)return find(pre,c[o][d],val,k,dep-1);40 else return find(pre,c[o][d^1],val|(1< ,greater > q;43 int main(){44 freopen(FILE".in","r",stdin);45 freopen(FILE".out","w",stdout);46 n=read(),K=read()*2;47 up(i,1,n)a[i]=read(),add(rt,a[i],30);48 up(i,1,n)vis[i]=1;49 up(i,1,n)q.push(make_pair(find(a[i],rt,0,++vis[i],30),i));50 up(t,1,K){51 pii k=q.top();q.pop();52 int i=k.second,key=k.first;53 if(t&1)printf("%d ",key);54 q.push(make_pair(find(a[i],rt,0,++vis[i],30),i));55 }56 57 return 0;58 }