BZOJ

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.