BZOJ 3261

不稳定的传送门

设$b[i]=a[1] \oplus a[2] \oplus \cdots \oplus a[i-1],b[1]=0$

$a[i] \oplus a[i+1] \oplus \cdots \oplus a[n] \oplus x=b[i] \oplus b[n+1] \oplus x$

后面的$b[n+1] \oplus x$是定值,所以题目就成了求$[l,r]$中使上面的式子最大的$i$

因为求的是最大,所以在可持久化Trie中往下走时,先看当前这一位能不能为$1$,能为$1$就走儿子$1$,否则走儿子$0$


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
program bzoj_3261;
const log=23;
var s:array[0..7500000*2]of record son:array[0..1]of longint; size:longint; end;
n,m,i,a,x,tot,l,r:longint;
b,root:array[1..600001]of longint;
c:char;
procedure insert(var t:longint;st,pos,base:longint);
var x:longint;
begin
inc(tot);
t:=tot;
s[t]:=s[base];
inc(s[t].size);
if pos<0 then exit;
x:=st>>pos and 1;
insert(s[t].son[x],st,pos-1,s[base].son[x]);
end;
function query(t1,t2,pos,st:longint):longint;
var x,y:longint;
begin
if pos<0 then exit(0);
x:=((st>>pos)and 1)xor 1;
y:=x xor 1;
if s[s[t2].son[x]].size=s[s[t1].son[x]].size then x:=x xor 1;
exit((x xor y)<<pos+query(s[t1].son[x],s[t2].son[x],pos-1,st));
end;
begin
readln(n,m);
b[1]:=0;
inc(n);
tot:=0;
s[0].son[0]:=0;
s[0].son[1]:=0;
s[0].size:=0;
insert(root[1],0,log,0);
for i:=2 to n do
begin
read(a);
b[i]:=b[i-1] xor a;
insert(root[i],b[i],log,root[i-1]);
end;
readln;
for i:=1 to m do
begin
read(c);
if c='A' then
begin
readln(a);
inc(n);
b[n]:=b[n-1]xor a;
insert(root[n],b[n],log,root[n-1]);
end else
begin
readln(l,r,x);
writeln(query(root[l-1],root[r],log,b[n] xor x));
end;
end;
end.