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
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
这题和Noi2010超级钢琴特别像。
首先把每个数都插进01Trie里，然后把每个对于每个数的异或值的第二小放入小根堆中(因为第一小一定是他自己)。
查询异或值的第k小和在线段树上二分查找第k小类似，维护0/1儿子的size，然后像线段树一样分类讨论一下。
我们从堆中取出当前最小的值，然后把这个位置的下一个最小值插进堆里，一直这样维护就行了。
因为一个最小值会被它的两个元素同时枚举到，所以我们只要在奇数位置上输出就行了。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <queue> #include <map> using namespace std; #define reg register inline int read() { int res = 0;char ch=getchar();bool fu=0; while(!isdigit(ch))fu|=(ch=='-'),ch=getchar(); while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48), ch=getchar(); return fu?-res:res; } #define mkp make_pair #define pii pair<int, int> #define N 100005 int n, K; int a[N]; int nxt[N*31][2], siz[N*31], tot; inline void ins(int v) { int now = 0; for (reg int i = 31 ; i >= 0 ; i --) { bool d = v & (1ll << i); if (!nxt[now][d]) nxt[now][d] = ++tot; now = nxt[now][d]; siz[now]++; } } int timc[N]; inline int Findk(int v, int k) { int now = 0, res = 0; for (reg int i = 31 ; i >= 0 ; i --) { bool d = v & (1ll << i); if (siz[nxt[now][d]] >= k) now = nxt[now][d]; else k -= siz[nxt[now][d]], now = nxt[now][d^1], res |= (1ll << i); } return res; } int main() { n = read(), K = read(); for (reg int i = 1 ; i <= n ; i ++) ins(a[i] = read()); priority_queue <pii, vector<pii>, greater<pii> > q; for (reg int i = 1 ; i <= n ; i ++) { q.push(mkp(Findk(a[i], 2), i)); timc[i] = 3; // printf("%d %d ",i, Findk(a[i], 2)); } for (reg int i = 1 ; i <= K<<1 ; i ++) { int tp = q.top().first, id = q.top().second;q.pop(); if (i & 1) printf("%d ", tp); if (timc[id] == n) continue; q.push(mkp(Findk(a[id], timc[id]), id)); timc[id]++; } return 0; }