P4735 最大异或和题解

题面

考虑异或可以表示成前缀和的形式，则 \(a[p]\oplus a[p+1]\oplus\ldots \oplus a[n]\oplus x=s[p-1]\oplus s[n] \oplus x\)。后面都是知道的，所以可以拿着 \(s[n]\oplus x\) 的值去01-trie上做匹配。注意到还有一个 \(p\in[l-1,r-1]\) 的限制，可以使用可持久化trie，查询第 \(r-1\) 个版本，再在每个节点记录一个 \(las\) 表示走到这个点的 \(l\) 的最大值，只走其中 \(las\geq l-1\) 的即可。

点击查看代码

#include<iostream>#include<cstdio>using namespace std;const int N=6e5+13,logN=21;int n,m,s[N],rt[N];struct Trie{int ch[N*logN][2],cnt,las[N*logN];inline int insert(int num){int now=rt[num-1],root=++cnt,p=root;las[p]=num;for(int i=24;i>=0;--i){int c=(s[num]&(1<<i)?1:0);ch[p][c^1]=ch[now][c^1];ch[p][c]=++cnt;p=cnt,now=ch[now][c];las[p]=num;}return root;}inline int query(int l,int r,int x){int p=rt[r];int res=0;if(!r) return x;for(int i=24;i>=0;--i){int c=(x&(1<<i)?1:0);if(ch[p][c^1]&&las[ch[p][c^1]]>=l) p=ch[p][c^1],res+=(1<<i);else p=ch[p][c];}return res;}}T;int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;++i){scanf("%d",&s[i]);s[i]^=s[i-1];rt[i]=T.insert(i);}while(m--){char op;int l,r,x;cin>>op;if(op=='A'){scanf("%d",&s[++n]);s[n]^=s[n-1];rt[n]=T.insert(n);}else{scanf("%d%d%d",&l,&r,&x);printf("%d\n",T.query(l-1,r-1,s[n]^x));}}return 0;}

免责声明：本网信息来自于互联网，目的在于传递更多信息，并不代表本网赞同其观点。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，并请自行核实相关内容。本站不承担此类作品侵权行为的直接责任及连带责任。如若本网有任何内容侵犯您的权益，请及时联系我们，本站将会在24小时内处理完毕。