「十二省联考2019」异或粽子

发表于 | 分类于 | | 浏览量： 次

粽子真好吃qwq。

传送门

洛谷P5283

BZOJ5495

题解

这题还是比较套路的吧。

令$S_i=a_1⊕a_2⊕\cdots⊕a_i$。

则$Al⊕A{l+1}⊕\cdots⊕Ar=S_r⊕S{l-1}$。

首先，对于每一个$r$，找到与$Sr$异或值最大的$S{l-1}$并把它们扔进一个堆里。

然后重复下面的步骤$K$次：

  • 取出堆顶的元素；

  • 更新堆顶元素所对应的$Sr$在删去当前与它异或值最大的$S{l-1}$后与它异或值最大的数；

  • 将更新过后的最大数重新丢进堆里；

可以通过可持久化Trie来完成这个维护的过程。

代码

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<queue>
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=500005,maxk=200005;
int n,K,idx[maxn],cnt[maxn];LL A[maxn],S[maxn],ans,Pow[35];
inline char nc()
{
	static const int S=1048576;static char buf[S],*L,*R;
	return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;
}
inline LL read()
{
	LL ret=0,f=1;char ch=nc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}
	return ret*f;
}
struct PersistentTrie
{
	int cnt,tot,R[maxn+maxk];
	struct Node{int siz,son[2];}Tree[maxn*33+maxk*33];
	inline int NewNode(){return ++tot;}
	inline int NewTree(){return ++cnt;}
	inline void Insert(LL num)
	{
		int pre=R[cnt],rt=R[NewTree()]=NewNode();
		for(int i=31;i>=0;i--)
		{
			Tree[rt]=Tree[pre];
			Tree[rt].siz++;
			if(num&Pow[i])
			{
				Tree[rt].son[1]=NewNode();
				rt=Tree[rt].son[1];pre=Tree[pre].son[1];
			}
			else
			{
				Tree[rt].son[0]=NewNode();
				rt=Tree[rt].son[0];pre=Tree[pre].son[0];
			}
		}
		Tree[rt]=Tree[pre];
		Tree[rt].siz++;
	}
	inline void Del(LL num,int pre)
	{
		int rt=R[NewTree()]=NewNode();pre=R[pre];
		for(int i=31;i>=0;i--)
		{
			Tree[rt]=Tree[pre];
			Tree[rt].siz--;
			if(num&Pow[i])
			{
				Tree[rt].son[1]=NewNode();
				rt=Tree[rt].son[1];pre=Tree[pre].son[1];
			}
			else
			{
				Tree[rt].son[0]=NewNode();
				rt=Tree[rt].son[0];pre=Tree[pre].son[0];
			}
		}
		Tree[rt]=Tree[pre];
		Tree[rt].siz--;
	}
	inline LL QueryMax(LL num,int rt)
	{
		LL ret=0;
		for(int i=31;i>=0;i--)
		{
			int nxt=!(bool)(num&Pow[i]);
			if(Tree[Tree[rt].son[nxt]].siz)
			{
				rt=Tree[rt].son[nxt];
				if(nxt) ret+=Pow[i];
			}
			else
			{
				rt=Tree[rt].son[!nxt];
				if(!nxt) ret+=Pow[i];
			}
		}
		return ret;
	}
}PT;
struct Ele
{
	int pos;LL num,sum;
	bool operator < (const Ele& b)const{return sum<b.sum;}
}tep;
inline void Solve()
{
	priority_queue<Ele> H;
	for(int i=1;i<=n;i++)
	{
		S[i]=S[i-1]^A[i];
		PT.Insert(S[i-1]);
		idx[i]=PT.cnt;
		tep.pos=i;
		tep.num=PT.QueryMax(S[i],PT.R[idx[i]]);
		tep.sum=tep.num^S[i];
		H.push(tep);
	}
	while(K--)
	{
		tep=H.top();H.pop();
		ans+=tep.sum;cnt[tep.pos]++;
		if(cnt[tep.pos]<tep.pos)
		{
			PT.Del(tep.num,idx[tep.pos]);
			idx[tep.pos]=PT.cnt;
			tep.num=PT.QueryMax(S[tep.pos],PT.R[idx[tep.pos]]);
			tep.sum=tep.num^S[tep.pos];
			H.push(tep);
		}
	}
}
int main()
{
	n=read();K=read();Pow[0]=1;
	for(int i=1;i<=n;i++) A[i]=read();
	for(int i=1;i<=31;i++) Pow[i]=Pow[i-1]*2;
	Solve();
	printf("%lld\n",ans);
	return 0;
}