浅谈 \(Trie\): https://www.cnblogs.com/AKMer/p/10444829.html
题目传送门: https://lydsy.com/JudgeOnline/problem.php?id=3261
假设现在所有数的异或和是 \(xor\_sum\),\(sum\_xor[i]\) 表示前 \(i\) 个数的异或和, 那么每次询问可以转化成:
在区间 \([l-1,r-1]\) 里面找一个 \(sum\_xor_i\), 使得 \(sum\_xor_i\oplus x\oplus xor\_sum\) 最大值.
我们已经知道了 \(x\oplus xor\_sum\) 的值, 只需要按照每一位去贪心地找 \(sum\_xor_i\) 的合适的值就行了.
由于是在区间内找有没有某一位存在我想要的, 显然就能想到可持久化了.
时间复杂度:\(O((n+m)*24)\)
空间复杂度:\(O((n+m)*24)\)
代码如下:
- #include <cstdio>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- const int maxn=3e5+5;
- char s[5];
- int rt[maxn<<1];
- int cnt,n,m,xor_sum;
- int read() {
- int x=0,f=1;char ch=getchar();
- for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
- for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
- return x*f;
- }
- struct Trie {
- int tot;
- struct node {
- int sum;
- int son[2];
- }p[maxn*48];
- void ins(int lst_id,int id,int v) {
- int lst=rt[lst_id],u;
- u=rt[id]=++tot;
- for(int i=24;~i;i--) {
- int c=v>>i&1;
- p[u].son[c]=++tot;
- u=p[u].son[c],lst=p[lst].son[c];
- p[u]=p[lst];p[u].sum++;
- }
- }
- void make_ans(int u2,int u1,int v) {
- int ans=0;
- for(int i=24;~i;i--) {
- int c=v>>i&1;
- int sum=p[p[u1].son[c^1]].sum;
- sum-=p[p[u2].son[c^1]].sum;
- if(!sum)ans=ans<<1,u1=p[u1].son[c],u2=p[u2].son[c];
- else ans=ans<<1|1,u1=p[u1].son[c^1],u2=p[u2].son[c^1];
- }
- printf("%d\n",ans);
- }
- }T;
- int main() {
- cnt=n=read(),m=read();
- for(int i=1;i<=n;i++) {
- int x=read();xor_sum^=x;
- T.ins(i-1,i,xor_sum);
- }
- for(int i=1;i<=m;i++) {
- scanf("%s",s+1);
- if(s[1]=='A') {
- int x=read();xor_sum^=x,cnt++;
- T.ins(cnt-1,cnt,xor_sum);
- }
- else {
- int l=read(),r=read(),x=read();
- if(r==1) {printf("%d\n",x^xor_sum);continue;}
- T.make_ans(rt[max(0,l-2)],rt[r-1],x^xor_sum);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2970222.html