记录编号	371248	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2015] Xor!	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	2.502 s
提交时间	2017-02-15 19:45:53	内存使用	25.11 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=50010;
struct A{
	int x,y,l,r,d;
	A(int x,int y,int l,int r,int d):x(x),y(y),l(l),r(r),d(d){}
	bool operator<(const A &a)const{return d<a.d;}
};
void build(int,int&,int);
int query(int,int,int);
int sm[maxn<<5]={0},ch[maxn<<5][2]={{0}},id[maxn<<5]={0},root[maxn]={0},cnt=0;
priority_queue<A>heap;
int n,k,a[maxn],x,y;
int main(){
	freopen("_xor!.in","r",stdin);
	freopen("_xor!.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		x=a[i];
		y=i;
		build(30,root[i],root[i-1]);
		if(i>1){
			y=query(30,root[i-1],root[0]);
			heap.push(A(i,y,1,i-1,a[i]^a[y]));
		}
	}
	while(k--){
		A t=heap.top();
		heap.pop();
		printf("%d\n",t.d);
		x=a[t.x];
		if(t.l<t.y){
			y=query(30,root[t.y-1],root[t.l-1]);
			heap.push(A(t.x,y,t.l,t.y-1,a[t.x]^a[y]));
		}
		if(t.r>t.y){
			y=query(30,root[t.r],root[t.y]);
			heap.push(A(t.x,y,t.y+1,t.r,a[t.x]^a[y]));
		}
	}
	return 0;
}
void build(int k,int &rt,int pr){
	sm[rt=++cnt]=sm[pr]+1;
	ch[rt][0]=ch[pr][0];
	ch[rt][1]=ch[pr][1];
	if(k==-1)id[rt]=y;
	else build(k-1,ch[rt][(x>>k)&1],ch[pr][(x>>k)&1]);
}
int query(int k,int rt,int pr){
	if(k==-1)return id[rt];
	else if(sm[ch[rt][((x>>k)&1)^1]]>sm[ch[pr][((x>>k)&1)^1]])return query(k-1,ch[rt][((x>>k)&1)^1],ch[pr][((x>>k)&1)^1]);
	else return query(k-1,ch[rt][(x>>k)&1],ch[pr][(x>>k)&1]);
}