洛谷P4735 最大异或和

电脑从拯救者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

上一篇:新生34场


下一篇:递归应用-字符串反转