OI题解 - 异或粽子(LOJ) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI题解 - 异或粽子(LOJ)

发表于 更新于 分类于 Valine：

早就该写了然后咕到这一次省选前才补题

# 题面

> LOJ 3048

# 解析

区间异或和可以前缀和，记前缀和数组为 $pre_i$，那么我们建一棵 TRIE 树，再把所有 $pre_i$（$i\in[0,n]$）往 TRIE 树上塞。

然后根据 TRIE 树上位运算的贪心策略，对于任意一个数 $x$，我们可以求出：$x\text{ xor }pre_i$ 的第 $t$ 大的值。

于是这样我们就可以做出这道题了？

我们先对每个 $x=pre_i$（$i\in[0,n]$） 计算 $x\text{ xor }pre_j$ 的第一大的值，记为 $val_i$，然后把 $val_i$ 塞到一个大根堆里。接下来连续进行 $2k$ 次操作：

  • 答案加上堆顶元素；
  • 取出堆顶，设堆顶是 $x=pre_i$ 时 $x\text{ xor }pre_j$ 的第 $rnk$ 大的值；
  • 在 TRIE 上计算 $x=pre_i$ 时 $x\text{ xor }pre_j$ 的第 $(rnk+1)$ 大的值；
  • 把该值塞进堆里；

答案除以二就是所求解。

可以知道我们第 $i$ 次取出的堆顶就是第 $i$ 大的区间异或和。又因为我们会重复计算 $pre_r\text{ xor }pre_{l-1}$ 和 $pre_{l-1}\text{ xor }pre_r$，即相同值计算了两次，故要取出前 $2k$ 大，并且答案要除以2。

> Trick.

  1. 区间异或和转为前缀异或和，再用TRIE贪心；
  2. 如果有若干个可重集合，而且可重集合的任何一个元素都容易计算，要求这些可重集合的并集中第 $k$ 大的元素。可以把每个集合中最大的元素插入到堆中，然后在该集合中删去这个最大值；每次取出堆顶元素，在对应的集合中再找最大值；重复计算 $k$ 次即得到答案。

# 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*Lucky_Glass*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=5e5+10;

int n,m;
ll val[N],pre[N];

struct TRIE{
	int ncnt,nxt[N*32][2],siz[N*32],rt;
	void Insert(int &u,const int &dep,const ll &num){
		if(!u) u=++ncnt;
		siz[u]++;
		if(dep<0) return;
		Insert(nxt[u][num>>dep&1],dep-1,num);
	}
	ll Query(const int &u,const int &dep,const ll &num,const int &rnk){
		if(dep<0) return 0;
		if(num>>dep&1)
			if(rnk<=siz[nxt[u][0]]) return Query(nxt[u][0],dep-1,num,rnk);
			else return Query(nxt[u][1],dep-1,num,rnk-siz[nxt[u][0]])|(1ll<<dep);
		else
			if(rnk<=siz[nxt[u][1]]) return Query(nxt[u][1],dep-1,num,rnk)|(1ll<<dep);
			else return Query(nxt[u][0],dep-1,num,rnk-siz[nxt[u][1]]);
	}
}Tr;

struct DATA{
	ll num;
	int idx,rnk;
	DATA(const ll &_n,const int &_i,const int &_r):num(_n),idx(_i),rnk(_r){}
};
bool operator <(const DATA &a,const DATA &b){return a.num<b.num;}

inline ll Ri(){
	register ll a=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') a=(a<<1)+(a<<3)+c-'0',c=getchar();
	return a;
}
priority_queue<DATA> que;
int main(){
	n=Ri(),m=Ri()*2;
	for(int i=1;i<=n;i++)
		pre[i]=pre[i-1]^(val[i]=Ri());
	Tr.Insert(Tr.rt,31,0);
	for(int i=1;i<=n;i++)
		Tr.Insert(Tr.rt,31,pre[i]);
	for(int i=0;i<=n;i++){
		ll res=Tr.Query(Tr.rt,31,pre[i],1)^pre[i];
		que.push(DATA(res,i,1));
	}
	ll ans=0;
	while(m--){
		ans+=que.top().num;
		int thi=que.top().idx,rnk=que.top().rnk;
		que.pop();
		if(rnk>n) continue;
		rnk++;
		ll res=Tr.Query(Tr.rt,31,pre[thi],rnk)^pre[thi];
		que.push(DATA(res,thi,rnk));
	}
	printf("%lld\n",ans/2);
	return 0;
}

THE END

Thanks for reading!