xor有一个很重要的性质就是A xor B xor B=A
所以这道题求[l,r]中p,使a[p] xor a[p+1] xor ... xor a[N] xor x 最大
就是=最大化a[1] xor ……a[n] xor x xor a[1] xor a[2] xor ……a[p-1]
令b[i]=a[1] xor a[2] xor ……a[i]
则最大化b[p] xor b[n] xor X p∈[l-1,r-1]
抛开区间,求b[p] xor Y的最大值我们需要用到trie树
由于是区间修改,所以要求我们对trie进行可持久化
类比主席树,我们对每个i都建立一棵trie树,不同的节点增开空间
在区间询问的时候,如果两棵树指向同一个节点,说明这一位上的值是不能取的,否则就按trie的贪心做
感觉可持久化就是对历史信息尽可能的保留,对新的值新开空间
var son:array[-..,..] of longint;
i,t,x,l,r,n,m:longint;
b,root:array[-..] of longint;
ch:char; procedure add(j,x:longint);
var i,a,b,y:longint;
begin
a:=root[j-];
b:=root[j];
for i:= downto do
begin
y:=x and ( shl i);
if y> then y:=;
inc(t);
son[b,y]:=t; //类比主席树
son[b,-y]:=son[a,-y];
a:=son[a,y];
b:=son[b,y];
end;
end; function ask(l,r,x:longint):longint;
var y,i,a,b:longint;
begin
a:=root[l];
b:=root[r];
ask:=;
for i:= downto do
begin
y:=x and ( shl i);
if y> then y:=;
if (son[b,-y]=) or (son[b,-y]=son[a,-y]) then //判断这位在区间内是否存在
begin
a:=son[a,y];
b:=son[b,y];
end
else begin
ask:=ask+ shl i;
a:=son[a,-y];
b:=son[b,-y];
end;
end;
end; begin
readln(n,m);
b[]:=;
t:=;
root[]:=;
x:=;
for i:= downto do
begin
inc(t);
son[x,]:=t;
x:=t;
end;
for i:= to n do
begin
read(x);
b[i]:=b[i-] xor x;
inc(t);
root[i]:=t;
add(i,b[i]);
end;
readln;
for i:= to m do
begin
read(ch);
if ch='A' then
begin
readln(x);
inc(n);
b[n]:=b[n-] xor x;
inc(t);
root[n]:=t;
add(n,b[n]);
end
else begin
readln(l,r,x);
x:=x xor b[n];
writeln(ask(l-,r-,x));
end;
end;
end.