【bzoj3689】异或之可持久化Trie树+堆

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目描述

给定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++中的“^”。

输入

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

输出

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

样例输入

4 5
1
1
3
4

样例输出

0 2 2 5 5

题解

可持久化Trie树+堆，和 bzoj2006 差不多

那道题要求的是区间内数的最大值，所以使用了ST表；这道题需要求区间内数与某数的最大异或和，所以需要使用可持久化Trie树。

具体实现：维护一个结构体存储5个变量t、l、r、p、v，分别代表：两个数中的第一个、两个数中的第二个的取值范围的左端、两个数中的第二个的取值范围的右端、最大异或和的第二个数的位置、最大异或和。将初始区间扔进以最大异或和为关键字的大根堆里，每次取出一个结构体，把v加到答案中，并计算(t,l,p-1)和((t,p+1,r)，再把它们扔回堆中。

时间复杂度$O(k\log n)$

#include <cstdio>

#include <queue>

#define N 200010

#define M 6000010

using namespace std;

struct data

{

	int t , l , r , p , v;

	data() {}

	data(int t0 , int l0 , int r0 , int p0 , int v0) {t = t0 , l = l0 , r = r0 , p = p0 , v = v0;}

	bool operator<(const data a)const {return v > a.v;}

}tmp;

priority_queue<data> q;

int a[N] , c[2][M] , si[M] , tag[M] , root[N] , tot;

int insert(int x , int p , int v)

{

	int i , y = ++tot , r = y;

	bool t;

	for(i = 1 << 30 ; i ; i >>= 1)

		t = v & i , c[t ^ 1][y] = c[t ^ 1][x] , c[t][y] = ++tot , x = c[t][x] , y = c[t][y] , si[y] = si[x] + 1;

	tag[y] = p;

	return r;

}

int query(int x , int y , int v)

{

	int i;

	bool t;

	for(i = 1 << 30 ; i ; i >>= 1)

	{

		t = v & i;

		if(si[c[t][y]] - si[c[t][x]]) y = c[t][y] , x = c[t][x];

		else y = c[t ^ 1][y] , x = c[t ^ 1][x];

	}

	return tag[y];

}

int main()

{

	int n , k , i , d;

	scanf("%d%d" ,  &n , &k);

	for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]) , root[i] = insert(root[i - 1] , i , a[i]);

	for(i = 1 ; i < n ; i ++ ) d = query(root[i] , root[n] , a[i]) , q.push(data(i , i + 1 , n , d , a[d] ^ a[i]));

	while(k -- )

	{

		tmp = q.top() , q.pop() , printf("%d " , tmp.v);

		if(tmp.p > tmp.l) d = query(root[tmp.l - 1] , root[tmp.p - 1] , a[tmp.t]) , q.push(data(tmp.t , tmp.l , tmp.p - 1 , d , a[d] ^ a[tmp.t]));

		if(tmp.r > tmp.p) d = query(root[tmp.p] , root[tmp.r] , a[tmp.t]) , q.push(data(tmp.t , tmp.p + 1 , tmp.r , d , a[d] ^ a[tmp.t]));

	}

	return 0;

}