BZOJ 2819

传送门

又是一道感人肺腑的题TAT…凭什么某++可以很舒服地写倍增,PASCAL却还要拿${\rm Tarjan}$卡时

首先,若许多堆石子的异或值为$0$,那么就没有先手必胜策略,因为后手的人总能把自己行动后的${\rm SG}$值变为$0$

那么题就成了查询路径上所有点权的异或值,即$W_{u\rightarrow root}\oplus W_{v\rightarrow root}\oplus W_{lca(u,v)}$

直接DFS序+树状数组即可

若修改一个点的点权,只会对其子树中的点有影响,只要修改进DFS序和出DFS序+1的位置就行了

没有读入优化真不爽 尼玛最大一组数据20M让PASCAL怎么读


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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
program bzoj_2819;
var n,i,a,b,tot,q,t:longint;
l:array[1..1000000]of record ed,pre:longint; end;
ll:array[1..1000000]of record ed,pre,id:longint; end;
lst,dep,st,pl,pr,lnk,x,y,lca:array[0..500000]of longint;
fa:array[0..500000]of longint;
bit:array[1..1000000]of longint;
ch:char;
ask,v:array[1..500000]of boolean;
procedure link(a,b:longint);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].ed:=b;
end;
procedure link_(a,b:longint);
begin
inc(tot);
ll[tot].pre:=lnk[a];
lnk[a]:=tot;
ll[tot].ed:=b;
ll[tot].id:=i;
end;
function findfa(x:longint):longint;
begin
if fa[x]<>x then fa[x]:=findfa(fa[x]);
exit(fa[x]);
end;
function c(x:longint):longint;
begin
exit(x and -x);
end;
function query(p:longint):longint;
begin
query:=0;
while p>0 do
begin
query:=query xor bit[p];
dec(p,c(p));
end;
end;
procedure modify(p,d:longint);
begin
while p<=n<<1 do
begin
bit[p]:=bit[p] xor d;
inc(p,c(p));
end;
end;
procedure dfs(t,f:longint);
var k:longint;
begin
v[t]:=true;
fa[t]:=t;
inc(tot);
pl[t]:=tot;
modify(tot,st[t]);
k:=lnk[t];
while k<>0 do
begin
if v[ll[k].ed] then lca[ll[k].id]:=findfa(ll[k].ed);
k:=ll[k].pre;
end;
k:=lst[t];
while k<>0 do
begin
if l[k].ed<>f then
begin
dep[l[k].ed]:=dep[t]+1;
dfs(l[k].ed,t);
fa[l[k].ed]:=t;
end;
k:=l[k].pre;
end;
inc(tot);
pr[t]:=tot;
modify(tot,st[t]);
end;
begin
readln(n);
for i:=1 to n do read(st[i]);
tot:=0;
for i:=1 to n-1 do
begin
readln(a,b);
link(a,b);
link(b,a);
end;
tot:=0;
readln(q);
for i:=1 to q do
begin
readln(ch,x[i],y[i]);
ask[i]:=(ch='Q');
if ch='Q' then
begin
link_(x[i],y[i]);
link_(y[i],x[i]);
end;
end;
tot:=0;
dfs(1,0);
for i:=1 to q do
begin
if ask[i] then
begin
t:=query(pl[x[i]]) xor query(pl[y[i]]) xor st[lca[i]];
if t=0 then writeln('No') else writeln('Yes');
end else
begin
modify(pl[x[i]],st[x[i]] xor y[i]);
modify(pr[x[i]]+1,st[x[i]] xor y[i]);
st[x[i]]:=y[i];
end;
end;
end.