【问题描述】
给出n个非负整数A[1]..A[n]，编程回答询问：
1 k x：询问 x xor A[i] (1<=i<=n) 中第k小的值。
2 k l r x：询问 x xor A[i] (l<=i<=r) 中第k小的值。
【输入格式】
第一行为整数n。 第二行为n个非负整数，表示A[1],A[2],…,A[n]。 第三行为整数m。 之后的m行，每行表示一种询问。
【输出格式】
对于每个询问，给出你的回答。
【输入样例】
5 1 2 3 4 5 2 1 4 3 2 2 3 5 2
【输出样例】
6 6
【数据范围】
n,m<=500000 A[i],x均在unsigned long long 范围，所有询问均合法
【来源】
Mr_he原创
一道可持久化的二进制trie树，写法类似权值线段树的Kth，只需要记录每个点的下面包含多少个数就可以了。
详细代码如下：
#include<cstdlib> #include<cstdio> #include<cstring> #include<iostream> #include<vector> using namespace std; typedef unsigned long long ull; const int maxn=500005; int root[maxn],s[maxn*32]={0},ch[maxn*32][2]={0},cnt=0,n; void up(int x) { s[x]=s[ch[x][0]]+s[ch[x][1]]; } void in(int pre,int &now,int i,ull x) { now=++cnt; ch[now][0]=ch[pre][0]; ch[now][1]=ch[pre][1]; s[now]=s[pre]; if(i<0) {s[now]++;return;} int d=(x>>i)&1; in(ch[pre][d],ch[now][d],i-1,x); up(now); } ull read() { ull x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x; } ull find(int pre,int now,int i,int k,ull &x) { if(i<0) return 0; int d=(x>>i)&1; int t=s[ch[now][d]]-s[ch[pre][d]]; if(t<k) { return find(ch[pre][d^1],ch[now][d^1],i-1,k-t,x)+((ull)1<<i); } else return find(ch[pre][d],ch[now][d],i-1,k,x); } char q[50]; void out(ull x) { if(!x) putchar('0'); int tot=0; while(x) { q[++tot]=x; x/=10; } for(int i=tot;i>=1;i--) putchar(q[i]+'0'); putchar('\n'); return; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); n=read(); ull x,ans; for(int i=1;i<=n;i++) { x=read(); in(root[i-1],root[i],63,x); } int l,r,k,id; int m=read(); while(m--) { id=read(); if(id==1) { k=read();x=read(); ans=find(root[0],root[n],63,k,x); } if(id==2) { k=read();l=read();r=read();x=read(); ans=find(root[l-1],root[r],63,k,x); } out(ans); } return 0; }