bzoj 3689: 异或之 字典树+堆

题意

给定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小的数。
2 <= n <= 100000； 1 <= k <= min{250000, n*(n-1)/2}；0 <= A[i] < 2^31

分析

先对所有数建一棵字典树，对字典树的每个节点记录这个节点下有多少个数，这样的话就资瓷查询一个数的第k小异或数了。
那么我们先把每个数的第二小数放进堆里面（第一小肯定是自己），每次取堆顶，加上当前的数是第k大，则把第k+1大扔进去即可。
当取堆顶的次数为奇数时输出，因为每个数会被取两次。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int N=100005;

int n,m,bin[35],cnt,ch[N*40][2],size[N*40],now[N],a[N];
struct data
{
int id,val;

bool operator < (const data &a) const
    {
return val>a.val;
    }
};
priority_queue<data> q;

int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}

void ins(int x)
{
int now=1;
for (int i=30;i>=0;i--)
    {
int y=(x&bin[i])>>i;
if (!ch[now][y]) now=ch[now][y]=++cnt;
else now=ch[now][y];
        size[now]++;
    }
}

int query(int d,int l,int x,int y)
{
if (l==-1) return 0;
int w=(x&bin[l])>>l;
if (ch[d][w]&&size[ch[d][w]]>=y) return query(ch[d][w],l-1,x,y);
else return bin[l]+query(ch[d][w^1],l-1,x,y-size[ch[d][w]]);
}

int main()
{
    bin[0]=1;
for (int i=1;i<=30;i++) bin[i]=bin[i-1]*2;
    n=read();m=read();cnt=1;
for (int i=1;i<=n;i++)
    {
        a[i]=read();
        ins(a[i]);
    }
for (int i=1;i<=n;i++) now[i]=2,q.push((data){i,query(1,30,a[i],2)});
for (int i=1;i<=m*2-1;i++)
    {
        data u=q.top();q.pop();
if (i&1) printf("%d ",u.val);
if (now[u.id]==n) continue;
        u.val=query(1,30,a[u.id],++now[u.id]);
        q.push(u);
    }
return 0;
}