洛谷P5283 异或粽子

洛谷P5283 异或粽子

题意：给出长为 \(n~(n \le 5 \times 10^5)\) 序列，显然有 \(\frac{n \times (n + 1)}{2}\) 个区间。求区间异或和前 \(k~(k \le min(\frac{n \times(n - 1)}{2},2 \times 10 ^ 5))\) 大的的和。

做法：套路先把区间异或转为前缀异或，于是变成前缀和 \(S_0 \sim S_n\) 这 \(n + 1\) 个元素的随机组合。排成矩阵发现，答案就在去掉对角线的右上方三角形中取。因为是对称的，且 \(k \le \frac{n \times (n - 1)}{2}\) ，\(0\) 肯定不会被取到，所以将 \(k <<= 1\) ，求出的就是两倍答案。

然后怎么做呢？对每个元素插 \(01trie\) ，这样我们是可以 \(\Theta(loga)\) 查找某元素的第 \(k\) 大异或和的，方法类似于在线段树上二分。我们先把每个元素最大异或和插入大根堆，每次取堆顶，若取出 \(S_i\) 的第 \(t\) 大，就插入 \(S_i\) 的第 \(t + 1\) 大。

#include
using namespace std;
#define int long long
const int N = 5e5 + 10;
int x; char v;
inline int read()
{
	x = 0;
	while(!isdigit(v)) v = getchar();
	while(isdigit(v)) x = (x << 1) + (x << 3) + v - 48, v = getchar();
	return x;
}
int n, k, a[N], now[N];
int ans;
int ch[N * 33][2], tot, mark[N * 33];
priority_queue > q;
inline void Insert(int v)
{
	int x = 0, c;
	for(int i = 31; i >= 0; --i)
	{
		c = ((v >> i) & 1);
		if(!ch[x][c]) ch[x][c] = ++tot;
		x = ch[x][c];
		++mark[x];
	}
}
inline int Query(int v, int rk)
{
	int x = 0, c;
	int res = 0;
	for(int i = 31; i >= 0; --i)
	{
		c = ((v >> i) & 1);
		if(mark[ch[x][c ^ 1]] >= rk) x = ch[x][c ^ 1], res += (1ll << i);//
		else rk -= mark[ch[x][c ^ 1]], x = ch[x][c];//
	}
	return res;
}
signed main()
{ 
    n = read(), k = read();
    Insert(0);
    for(int i = 1; i <= n; ++i) x = read(), a[i] = a[i - 1] ^ x, Insert(a[i]);//
    for(int i = 0; i <= n; ++i) q.push(make_pair(Query(a[i], ++now[i]), i));
    k <<= 1;
    for(int i = 1; i <= k; ++i)
    {
    	ans += q.top(). first; x = q.top().second; q.pop();
    	if(now[x] < n)
    		q.push(make_pair(Query(a[x], ++now[x]), x));
	}
	cout << (ans >> 1);
	return 0;
}