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的贪心做
感觉可持久化就是对历史信息尽可能的保留，对新的值新开空间
1 var son:array[-1..30000010,0..1] of longint; 2 i,t,x,l,r,n,m:longint; 3 b,root:array[-1..610000] of longint; 4 ch:char; 5 6 procedure add(j,x:longint); 7 var i,a,b,y:longint; 8 begin 9 a:=root[j-1]; 10 b:=root[j]; 11 for i:=23 downto 0 do 12 begin 13 y:=x and (1 shl i); 14 if y>0 then y:=1; 15 inc(t); 16 son[b,y]:=t; //类比主席树 17 son[b,1-y]:=son[a,1-y]; 18 a:=son[a,y]; 19 b:=son[b,y]; 20 end; 21 end; 22 23 function ask(l,r,x:longint):longint; 24 var y,i,a,b:longint; 25 begin 26 a:=root[l]; 27 b:=root[r]; 28 ask:=0; 29 for i:=23 downto 0 do 30 begin 31 y:=x and (1 shl i); 32 if y>0 then y:=1; 33 if (son[b,1-y]=0) or (son[b,1-y]=son[a,1-y]) then //判断这位在区间内是否存在 34 begin 35 a:=son[a,y]; 36 b:=son[b,y]; 37 end 38 else begin 39 ask:=ask+1 shl i; 40 a:=son[a,1-y]; 41 b:=son[b,1-y]; 42 end; 43 end; 44 end; 45 46 begin 47 readln(n,m); 48 b[0]:=0; 49 t:=1; 50 root[0]:=1; 51 x:=1; 52 for i:=23 downto 0 do 53 begin 54 inc(t); 55 son[x,0]:=t; 56 x:=t; 57 end; 58 for i:=1 to n do 59 begin 60 read(x); 61 b[i]:=b[i-1] xor x; 62 inc(t); 63 root[i]:=t; 64 add(i,b[i]); 65 end; 66 readln; 67 for i:=1 to m do 68 begin 69 read(ch); 70 if ch='A' then 71 begin 72 readln(x); 73 inc(n); 74 b[n]:=b[n-1] xor x; 75 inc(t); 76 root[n]:=t; 77 add(n,b[n]); 78 end 79 else begin 80 readln(l,r,x); 81 x:=x xor b[n]; 82 writeln(ask(l-2,r-1,x)); 83 end; 84 end; 85 end. 86 87