BZOJ 3123 「SDOI2013」森林

这题……半年前写了没调出来……

首先不考虑第一个操作,这不就是「Count on a Tree」?
沿用之前的想法,把路径信息转化为到根的路径信息相减。

那么考虑连边,即合并。
于是——
启(大)发(力)式 合 并!

首先用 dsu 找根,然后在合并的时候先判大小,把小的接到大的上去,均摊分析下最多合并 \(O(\log n)\) 次。
然后 DFS 更新重儿子和重链顶(是的没错我用树剖做 LCA)以及主席树。

树剖常数还是比 LCT 和倍增小很多的……
目前 BZOJ 第三优解。

代码:

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
126
127
#include <cstdio>
#include <algorithm>
#define ls(p) seg[p].ls
#define rs(p) seg[p].rs
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
while(ch < '0' || ch > '9')
w |= ch == '-',ch = gc();
while(ch >= '0' && ch <= '9')
x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
w ? x = -x : x;
}

const int N = 8e4;
int n,m,t,lastans;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
int a[N + 5],ind[N + 5],len;
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v;
pre[tot] = first[u];
first[u] = tot;
}
struct node
{
int sum;
int ls,rs;
} seg[(N << 7) + 10];
void insert(int x,int &p,int tl,int tr)
{
static int tot = 0;
seg[++tot] = seg[p],p = tot,++seg[p].sum;
if(tl == tr)
return ;
int mid = tl + tr >> 1;
x <= mid ? insert(x,ls(p),tl,mid) : insert(x,rs(p),mid + 1,tr);
}
int query(int k,int x,int y,int lca,int fa_lca,int tl,int tr)
{
if(tl == tr)
return tl;
int sum = seg[ls(x)].sum + seg[ls(y)].sum - seg[ls(lca)].sum - seg[ls(fa_lca)].sum;
int mid = tl + tr >> 1;
if(k <= sum)
return query(k,ls(x),ls(y),ls(lca),ls(fa_lca),tl,mid);
else
return query(k - sum,rs(x),rs(y),rs(lca),rs(fa_lca),mid + 1,tr);
}
int fa[N + 5],dep[N + 5],sz[N + 5],son[N + 5],top[N + 5],fat[N + 5];
inline int get(int x)
{
return !fat[x] ? x : fat[x] = get(fat[x]);
}
int rt[N + 5];
void dfs(int p)
{
insert(a[p],rt[p] = rt[fa[p]],1,len);
sz[p] = 1,son[p] = 0;
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
{
fa[to[i]] = fat[to[i]] = p,dep[to[i]] = dep[p] + 1,dfs(to[i]),sz[p] += sz[to[i]];
if(!son[p] || sz[to[i]] > sz[son[p]])
son[p] = to[i];
}
}
void get_top(int p)
{
if(son[p])
top[son[p]] = top[p],get_top(son[p]);
for(register int i = first[p];i;i = pre[i])
if((to[i] ^ fa[p]) && (to[i] ^ son[p]))
top[to[i]] = to[i],get_top(to[i]);
}
inline void link(int u,int v)
{
add(u,v),add(v,u);
if(sz[get(u)] < sz[get(v)])
swap(u,v);
fa[v] = fat[v] = u,dep[v] = dep[u] + 1,dfs(v),top[v] = v,get_top(v);
}
inline int getlca(int x,int y)
{
while(top[x] ^ top[y])
dep[top[x]] > dep[top[y]] ? x = fa[top[x]] : y = fa[top[y]];
return dep[x] < dep[y] ? x : y;
}
int main()
{
read(n),read(n),read(m),read(t);
for(register int i = 1;i <= n;++i)
read(a[i]),ind[i] = a[i];
sort(ind + 1,ind + n + 1),len = unique(ind + 1,ind + n + 1) - ind - 1;
for(register int i = 1;i <= n;++i)
a[i] = lower_bound(ind + 1,ind + len + 1,a[i]) - ind;
int u,v;
while(m--)
read(u),read(v),add(u,v),add(v,u);
for(register int i = 1;i <= n;++i)
if(!fa[i])
dep[i] = 1,dfs(i),top[i] = i,get_top(i);
char op;
int x,y,k;
while(t--)
{
op = 0;
while(op < 'A' || op > 'Z')
op = gc();
if(op == 'Q')
{
read(x),read(y),read(k),x ^= lastans,y ^= lastans,k ^= lastans;
int lca = getlca(x,y);
printf("%d\n",lastans = ind[query(k,rt[x],rt[y],rt[lca],rt[fa[lca]],1,len)]);
}
else
read(x),read(y),link(x ^= lastans,y ^= lastans);
}
}