前言:
古早东西,小点声笑。
进入正题
嘿嘿,这回有题面链接啦:3 2 1 上链接!
虽然题面哥是背刺哥,但是那也得先看题面哥,谁叫我们对题面哥爱得深沉呢~(好恶心…)
又是一个强制在线(不是 出题人咋这么喜欢强制爱呢【翻白眼】),来吧又是一年可持久化……等等,这次好像用的不是可持久化线段树而是另一位美女姐姐可持久化trie树!
我们先来看看这位美女姐姐的使用说明。嗯……和主席树大神差不多,都是要建新点连边巴拉巴拉……
那么我们的答题思路是啥,别着急,我还没有思路,不过别慌,优势在我们!异或吗?有点意思!让我们找出它的天敌—— 二次元 二进制!那么思路很显然了:建一个01trie树,如果有修改就加点;如果让查询,就从根节点开始找跟他不一样的就行(如果有的话)。那你会问了,他让求的不是区间内吗?小case,类前缀和就是救世神!!!
是题面哥改邪归正了还是美女姐姐太厉害了,感觉这题说到这就差不多了,有种“悠然心会,妙处难与君说”的无力感。罢了罢了,世事当如此啊,至于更多奥妙 (且听下回再说) ,徒儿你自己去代码里悟去吧!
#include<bits/stdc++.h>
using namespace std;
const int N=600000+10;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch-'0');ch=getchar();}return x*f;}
inline void write(int x){if(x<0)x*=-1,putchar('-');if(x>9)write(x/10);putchar(x%10+'0');return;}
int n,m,siz[N<<5],ch[N<<5][2],s[N<<1],tot,rt[N<<1],a,l,r,k,x;char op;
void add(int u,int v,int pos,int x){//新根节点 旧根节点 二进制下第pos位 十进制下数为x if(pos<0) return ;//我嘞个伪数 int i=(x>>pos)&1;//此处妙不可言 直接就找出了二进制下对应的那个数 妙啊!妙啊! ch[u][i]=++tot;//改动的点要改动 ch[u][i^1]=ch[v][i^1];//不改动的点不要改动 siz[ch[u][i]]=siz[ch[v][i]]+1;//新加个点 尺寸变大 add(ch[u][i],ch[v][i],pos-1,x);//递归
}//单点修改
int query(int u,int v,int pos,int x){同上 if(pos<0) return 0;//伪数+1 int i=(x>>pos)&1;//妙啊!妙啊!×INF if(siz[ch[u][i^1]]-siz[ch[v][i^1]]) //如果不一样(我们不一样!) return (1<<pos)+query(ch[u][i^1],ch[v][i^1],pos-1,x);//递归且加(1<<pos)因为此处有贡献 else return query(ch[u][i],ch[v][i],pos-1,x);//否则 直接递归
}
signed main(){n=read();m=read();//题面哥的要求 rt[0]=++tot;add(rt[0],0,25,0);//先把0爷塞进去 防止美女姐姐空闲着无聊 for(int i=1;i<=n;i++){a=read();s[i]=s[i-1]^a;//你看她像不像你那还活着的白月光(前缀和) rt[i]=++tot;add(rt[i],rt[i-1],25,s[i]);//美女姐姐的老套路啦 }for(int i=1;i<=m;i++){cin>>op;//无理取闹的题面哥+1 if(op=='A'){x=read();n++;s[n]=s[n-1]^x;rt[n]=++tot;add(rt[n],rt[n-1],25,s[n]);//同上 }if(op=='Q'){l=read()-1;r=read()-1;k=read();//因为k已经异或过s[n]了,所以l和r只能遗憾-1 式子证明见下 (其实你举个例子手膜一下就成) if(l==0) write(query(rt[r],0,25,k^s[n]));//防止下标出现负值 美女姐姐会迷路的 else write(query(rt[r],rt[l-1],25,k^s[n]));puts(" ");//熟悉的换行兄 }}return 0;
}/*
s[1] = a[0] xor a[1]
s[p] = s[p - 1] xor a[p]
a[p] xor a[p + 1] xor ... xor a[N] xor x = s[p - 1] xor s[N] xor x
a[p] xor a[p + 1] xor ... xor a[N] xor x = s[p - 1] xor s[N] xor x
当l <= p <= r时,求p,使s[p - 1] xor s[N] xor x最大
*/