[bzoj 3689] 异或之

一个非负整数数列A, 求 Ai xor Aj (1≤i<j≤n) 的前k小. (2≤n≤10^5, 1≤k≤min{2.5*10^5, n*(n-1)/2}) 和 <NOI 2010 超级钢琴> 类似. 用堆维护五元组 (x, l, r, j, v), 表示x与A[l..r]中的A[j]异或, 得到最小值v. 每从堆顶取出一个五元组, 就新加入两个 (如果存在): (x, l, j-1, j', v'), (x, j+1, r, j'', v'').

求v用可持久化Trie实现. 但是本题还要求对应的下标j, 所以在Trie的叶子结点加一个时间戳.

{% raw %}
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)
#define bin(x, k) ((x)>>(k)&1)
using namespace std;

const int D = 31, MAX_N = 1e5;

struct Node {
	Node* ch[2];
	int v, t;
} nodes[(D+1)*MAX_N+1], * nil = nodes, * root[MAX_N+1] = {nil};

inline Node* new_node(const Node& x)
{
	static Node* cur = nodes + 1;
	*cur = x;
	return cur++;
}

void insert(Node* &o, Node* p, int x, int k, int tm)
{
	o = new_node(*p);
	++o->v;
	if (k < 0) return o->t = tm, void();
	int b = bin(x, k);
	insert(o->ch[b], p->ch[b], x, k-1, tm);
}

int query(Node* o, Node* p, int x, int k, int& tm)
{
	if (k < 0) return tm = o->t, 0;
	int b = bin(x, k);
	return o->ch[b] - p->ch[b] ? query(o->ch[b], p->ch[b], x, k-1, tm)
		: 1<<k | query(o->ch[b^1], p->ch[b^1], x, k-1, tm);
}

inline void init()
{
	*nil = (Node){{nil, nil}, 0, 0};
}

struct Five {
	int x, l, r, j, v;
	Five(int x1, int l1, int r1): x(x1), l(l1), r(r1)
	{
		v = query(root[r], root[l-1], x, D-1, j);
	}
	bool operator>(const Five& rhs) const
	{
		return v > rhs.v;
	}
};

int A[MAX_N+1];
priority_queue<Five, vector<Five>, greater<Five> > Q;

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	init();
	For (i, 1, n) {
		scanf("%d", &A[i]);
		insert(root[i], root[i-1], A[i], D-1, i);
	}
	For (i, 2, n)
		Q.push(Five(A[i], 1, i-1));
	For (i, 1, k) {
		Five f = Q.top();
		Q.pop();
		printf("%d", f.v);
		if (i != k) putchar(' ');
		if (f.j > f.l)
			Q.push(Five(f.x, f.l, f.j-1));
		if (f.j < f.r)
			Q.push(Five(f.x, f.j+1, f.r));
	}
	return 0;
}
{% endraw %}