bzoj 3689 异或之

Description

给定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小的数。
注：xor对应于pascal中的“xor”，C++中的“^”。

Input

第一行2个正整数 n,k，如题所述。
以下n行，每行一个非负整数表示A[i]。

Output

共一行k个数，表示前k小的数。

Sample Input

4 5

1

1

3

4

Sample Output

0 2 2 5 5

HINT

【样例解释】

1 xor 1 = 0 (A[1] xor A[2])

1 xor 3 = 2 (A[1] xor A[3])

1 xor 4 = 5 (A[1] xor A[4])

1 xor 3 = 2 (A[2] xor A[3])

1 xor 4 = 5 (A[2] xor A[4])

3 xor 4 = 7 (A[3] xor A[4])

前5小的数：0 2 2 5 5

【数据范围】

对于100%的数据，2 <= n <= 100000； 1 <= k <= min{250000, n*(n-1)/2}；

0 <= A[i] < 2^31

题解

这题感觉很强势啊。

首先是对于每个数拆成01串，建个Trie树。在每个节点上面存下它子树里有多少个is_end。

这样就可以知道每个串的第k小异或值：从Trie树往下走，siz大于k就k减掉siz走另一半，小于就直接按照这个串向下遍历。

考虑维护一个小根堆，先把所有串的第二小的串压到堆里面（第一小是它和它自己），k次取出堆顶的输出，假如这是第x小的那么再把第x+1小的压进去。

但是发现每个串都会出现两次（正着和反着异或相同），那就取出2k次，奇数次的时候输出。

#include <cstdio>
#include <queue>
#define N 100010
using namespace std;
struct ques
{
    int k,v,a;
};
bool operator<(ques a,ques b)
{
    return a.v>b.v;
}
priority_queue<ques>que;
int ch[N*30][2],siz[N*30],root=1,sz=1,a[N],n,k;
void build(int x)
{
    int now=root;
    for (int i=30;i>=0;now=ch[now][(x&(1<<i))>>i],siz[now]++,i--)
        if (!ch[now][(x&(1<<i))>>i])
            ch[now][(x&(1<<i))>>i]=++sz;
}
int query(int x,int k)
{
    int now=root,temp=0;
    for (int i=30;i>=0;i--)
        if (siz[ch[now][(x&(1<<i))>>i]]>=k)
            now=ch[now][(x&(1<<i))>>i];
        else
            k-=siz[ch[now][(x&(1<<i))>>i]],
            now=ch[now][((x&(1<<i))>>i)^1],
            temp+=(1<<i);
    return temp;
}
main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]),build(a[i]);
    for (int i=1;i<=n;i++)
    {
        ques t;
        t.v=query(a[i],2),t.k=2,t.a=a[i];
        que.push(t);
    }
    for (int i=1;i<=(k<<1);i++)
    {
        ques now=que.top();que.pop();
        if (i&1)
            printf("%d ",now.v);
        if (now.k==n)
            continue;
        now.k++,now.v=query(now.a,now.k);
        que.push(now);
    }
}