BZOJ

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.