大森林

有趣的LCT题

题目链接

写在前面的一些结论:

  1. 合法的$2$操作只会在一段连续的区间内发生,所以合法$2$操作也只会在一段区间内发生,因此我们可以把更换生长节点的区间,和加点区间取并,使$2$操作一定合法

  2. 如果$2$操作一定合法,加点操作区间从l~r变为1~n并不影响答案

  3. 一个询问在该询问进入时处理,和之后处理,答案并不改变,并且只有涉及到该树的操作才会对这个询问产生影响

结论是显然的

知道这些之后,来考虑如何解决;

一个想法

可以基于上面结论,产生一个愚蠢的想法

设$x$为$2$操作后的生长节点,$y$为之前的

将$2$操作拆成两次:

  1. 在$l$处,将之后加入所有点,换到$x$下面
  2. 在$r+1$处,将之后加入所有点,换回$y$下面

然后将询问和$2$操作按位置排序,从1~n扫一遍,依次处理就得到了$O(n^{2})$的优秀做法

那么如何优化

虚点!!!

对每一个$2$操作建一个虚点,每个虚点的父节点是前一个虚点,第一个虚点的父亲是1

每一次加点就加到当前最后一个虚点下面就好了。

每次移动就直接将该$2$操作对应的虚点及其子树移到新的生长节点下然而还是T

统计答案

我们让虚点权值为0,实点为1

设一个点i到根路径上权值和为 $S_{i}$(包含自身权值)

$dis(u,v)=S_{u}+S_{v}-2S_{lca}$

大家举几个栗子,想象一下,就知道这是对的。我不会证

LCT大法吼!!!

移动子树相当于换父亲,LCT就可以了。

但是此处LCT 不能换根,因为有虚点,不同于普通树上路径,所以根的位置对答案会产生影响。

此处cut操作一定是儿子cut父亲,所以直接cut掉就可以了,like this

1
access(u);splay(u);fa[son[u][0]]=0,son[u][0]=0;

而link操作也一定是一颗树的根去link,所以也直接link就好了,像这样

1
access(v),splay(v),fa[v]=u;

然后就愉快的A了此题,时间复杂度$O(nlogn)$

代码

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
/*
Author: zxy_hhhh
date: 2018/12/07
*/
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#define rep(x, a, b) for (int x = int(a); x <= (int)(b); x++)
#define drp(x, a, b) for (int x = int(a); x >= (int)(b); x--)
#define cross(x, a) for (int x = hd[a]; x; x = nx[x])
#define ll long long
inline ll rd() {
ll _x = 0;
int _ch = getchar(), _f = 1;
for (; !isdigit(_ch) && (_ch != '-') && (_ch != EOF); _ch = getchar())
;
if (_ch == '-') {
_f = 0;
_ch = getchar();
}
for (; isdigit(_ch); _ch = getchar()) _x = _x * 10 + _ch - '0';
return _f ? _x : -_x;
}
void write(ll _x) {
if (_x >= 10)
write(_x / 10), putchar(_x % 10 + '0');
else
putchar(_x + '0');
}
inline void wrt(ll _x, char _p) {
if (_x < 0) putchar('-'), _x = -_x;
write(_x);
if (_p) putchar(_p);
}
#define maxn 400005
struct LCT {
int son[maxn][2], val[maxn], sum[maxn], fa[maxn], cnt;
inline bool isroot(int x) {
return son[fa[x]][1] != x && son[fa[x]][0] != x;
}
inline void update(int x) {
sum[x] = sum[son[x][0]] + sum[son[x][1]] + val[x];
}
inline void rotate(int x) {
int y = fa[x], z = fa[y], d = son[y][1] == x;
if (!isroot(y)) son[z][son[z][1] == y] = x;
fa[y] = x, fa[x] = z;
fa[son[x][!d]] = y, son[y][d] = son[x][!d];
son[x][!d] = y;
update(y), update(x);
}
inline void splay(int x) {
for (; !isroot(x);) {
int y = fa[x], z = fa[y];
if (!isroot(y))
(son[y][1] == x) ^ (son[z][1] == y) ? rotate(x) : rotate(y);
rotate(x);
}
}
inline int access(int x) {
int t = 0;
for (; x; t = x, x = fa[x]) splay(x), son[x][1] = t, update(x);
return t;
}
inline void link(int u, int v) { fa[v] = u; }//因为先有cut所以可以不access
inline void cut(int u) {
access(u);
splay(u);
fa[son[u][0]] = 0, son[u][0] = 0;
}
inline int dis(int x, int y) {
int Sum = 0;
access(x);
splay(x);
Sum += sum[x];
int lca = access(y);
splay(y);
Sum += sum[y];
access(lca);
splay(lca);
Sum -= sum[lca] << 1;
return Sum;
}
inline void changefa(
int x, int y) // xxc's fahter was hje before,but now his father is me
{
cut(x);
link(y, x);
}
inline int getfather(int x) {
access(x);
splay(x);
return son[x][0];
}
inline int new_node(int x) {
sum[++cnt] = x, val[cnt] = x;
return cnt;
}
} lct;
int to[maxn];
int cl[maxn], cr[maxn], ans[maxn];
int n, m, p, r, cnt, QwQ;
struct Query {
int op, w, x, y, id;
bool operator<(const Query &B) const {
return (w < B.w) || (w == B.w && op < B.op);
}
} Q[maxn << 1];
int main() {
n = rd(), m = rd();
to[1] = lct.new_node(1);
lct.link(1, lct.new_node(0));
cl[1] = 1, cr[1] = n;
int now = 2, w = 1;
rep(i, 1, m) {
int op = rd();
if (op == 0) {
cl[++w] = rd(), cr[w] = rd();
lct.link(now, to[w] = lct.new_node(1));
} else if (op == 1) {
int l = rd(), r = rd(), x = rd(), pre = now;
l = std::max(l, cl[x]), r = std::min(r, cr[x]);
if (l > r) continue;
now = lct.new_node(0);
Q[++cnt].op = 1, Q[cnt].w = l, Q[cnt].x = now, Q[cnt].y = to[x];
Q[++cnt].op = 1, Q[cnt].w = r + 1, Q[cnt].x = now, Q[cnt].y = pre;
lct.link(pre, now);
} else {
Q[++cnt].w = rd();
int x = rd(), y = rd();
Q[cnt].op = 2, Q[cnt].x = x, Q[cnt].y = y;
Q[cnt].id = ++QwQ;
}
}
std::sort(Q + 1, Q + 1 + cnt);
rep(i, 1, cnt) {
if (Q[i].op == 1)
lct.changefa(Q[i].x, Q[i].y);
else
ans[Q[i].id] = lct.dis(to[Q[i].x], to[Q[i].y]);
}
rep(i, 1, QwQ) wrt(ans[i], '\n');
}
avatar
小清新数据结构题

  1. 1. 写在前面的一些结论:
  2. 2. 一个想法
  3. 3. 那么如何优化
    1. 3.1. 虚点!!!
    2. 3.2. 统计答案
    3. 3.3. LCT大法吼!!!
  4. 4. 代码