电脑从拯救者y7000p 2019换到了m1 air,不想在m1上再折腾一遍hexo,索性就用cnblog了...
信誓旦旦的学了可持久化Trie和01Trie来搞,结果出了一点问题,被卡了好久
先随便糊了一个暴力,用pre记一下异或前缀和,Xor表示异或总和
pre[i]^Xor就是 (i+1)~n的异或和
这么裸的一个暴力居然给了73分,11个点wa了3个点,
#include <bits/stdc++.h>
using namespace std;
int Xor=0;
int n,m;
int a[600010],pre[600010];
inline int read() {
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9') f=(ch=='-')?-1:1,ch=getchar();
while(ch<='9'&&ch>='0') x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
return x*f;
}
int main() {
n=read(),m=read();
for (int i=1;i<=n;i++) {
cin>>a[i]; Xor^=a[i];
pre[i]=pre[i-1]^a[i];
}
char op;
int l,r,x;
for (int i=1;i<=m;i++) {
cin>>op;
if(op=='A') {
x=read();
a[++n]=x;
Xor^=x;
pre[n]=pre[n-1]^x;
} else {
int Max=0;
l=read(), r=read(), x=read();
for (int i=l; i<=r; i++) {
Max=max(Max,pre[i-1]^Xor^x);
}
cout<<Max<<endl;
}
}
return 0;
}
然后考虑做一点简单的优化,最好是能够像最大异或数对那样维护一个01Trie,这样对于每个x都能速查
如果l=1,r=n,那么只要把全部的pre^Xor放到Trie里面,然后差x能取到的最大值
但是现在l,r是有变动的,所以我们要维护多版本的01Trie,只有一个端点还是比较简单的,但是两端都在动,怎么可持久化这问题就比较头疼
就是要找一个维护的方法,每次给出l,r,我们都能拿到由pre[l-1]^Xor pre[l]^Xor ... pre[r-1]^Xor构成的01Trie