题目描述：

给定n个非负整数A[1], A[2], ……, A[n]。

对于每对(i, j)满足1 <= i < j <= n，得到一个新的数A[i] xor A[j]，这样共有n*(n-1)/2个新的数。求这些数（不包含A[i]）中前k小的数。

题解：

建一棵01Trie树，然后把所有数扔进去。

将所有数的当前相关最小值插入优先队列，每次弹出来一个。

因为同一对会出现两次，所以我们只能选取奇数次弹出的点。

每弹出一个就将相关数的更小值插进去。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define N 100050#define ll long longinline int rd(){    int f=1,c=0;char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();}    return f*c;}int n,k,a[N],rt[N],sum;struct node{    int x;    ll v;    node(){}    node(int x,ll v):x(x),v(v){}    friend bool operator < (node a,node b)    {        return a.v>b.v;    }};priority_queue
         
          que;int dep[N];struct Trie{    int tot,siz[35*N],ch[35*N][2];    void insert(int x)    {        int u=1;        for(int i=30;i>=0;i--)        {            int c = (x>>i)&1;            siz[u]++;            if(!ch[u][c])ch[u][c]=++tot;            u=ch[u][c];        }        siz[u]++;    }    ll query(int x,int k)    {        ll ret = 0;        int u = 1;        for(int i=30;i>=0;i--)        {            int c = (x>>i)&1;            if(siz[ch[u][c]]>=k)            {                u=ch[u][c];            }else            {                ret|=(1ll<