Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP3348 [ZJOI2016]大森林

Posted on
Symbols count in article: 3.4k Reading time ≈ 3 mins.

LCT + 虚点

大森林

思路

首先直接模拟总点数到达 $O(nm)$ 时空都爆炸，但考虑到询问和改变生长节点的操作，我们又必须把所有点搞出来， 套用分块中常见的逐块处理思想，我们同一时刻只维护一棵树，处理完该树的所有询问后变成下一棵，则空间变成 $O(n + m)$

考虑时间，每次重新建树是爆炸的，想办从上一棵树直接变成下一棵，那么我们需要支持增加/删除节点、子树移动，并且所有操作中根保持不变

发现询问保证节点存在，再考虑到增加节点的编号方式，其实完全不必支持删除节点，我们一开始把所有节点都增加出来，反正不会询问非法的节点，且非法的节点也不会在某两条合法节点的路径上（合法节点只加在合法节点后面）

那么我们就只需支持子树移动即可，好像有某个用欧拉环游序的动态树专门支持该操作，但其实我们可以直接用 LCT ，具体的，每次生长我们都建虚点，让其生长在虚点上，那么移动虚点就是带着生长的节点移动

最后考虑询问，我们 LCT 维护一个 $dep$ （虚点不贡献），那么答案就是两个点的 $dep$ 和减去 $lca$ 的 $dep$ 的二倍，要注意这个 $dep$ 是其实是 splay 中的 $si$ ，要求真正的 $dep$ 要先 $access$ 到根再 $splay(x)$ 一下，这样 $x$ 的 $si$ 就等于 $x$ 的 $dep$ ；而求 $lca$ 可以先 $access(x)$ 再 $access(y)$ ，第二次最后遇到的实链上的节点就是 $x, y$ 的 $lca$

时间复杂度 $O(m \log n)$

代码

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
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
const int N = 4e5 + 100;
int n, m;
std::vector<std::pair<int, int>> ans, live;
struct LCT //不换根LCT
{
    struct Node
    {
        Node *ch[2], *fa;
        int si;
        bool be;
    } tr[N];
    const Node _null = (Node){nullptr, nullptr, nullptr, 0, false};
    Node *null = (Node*)&_null, *tot = tr;
    static Node ttry;
    LCT(){ ttry = Node{}; }
    Node* _new(bool be)
    {
        *tot = (Node){null, null, null, be, be};
        return tot++;
    }
    void up(Node *x){ x->si = x->ch[0]->si + x->ch[1]->si + x->be; }
    bool is_rt(Node *x){ return x->fa->ch[0] != x && x->fa->ch[1] != x; }
    void rot(Node *x)
    {
        Node *y = x->fa, *z = y->fa;
        int k = y->ch[1] == x;
        if (!is_rt(y)) z->ch[z->ch[1] == y] = x;
        x->fa = z;
        y->ch[k] = x->ch[k ^ 1], x->ch[k ^ 1]->fa = y;
        x->ch[k ^ 1] = y, y->fa = x;
        up(y), up(x);
    }
    void splay(Node *x)
    {
        Node *y, *z;
        while (!is_rt(x))
        {
            y = x->fa, z = y->fa;
            if (!is_rt(y)) (y->ch[1] == x) ^ (z->ch[1] == y) ? rot(x) : rot(y);
            rot(x);
        }
    }
    Node* access(Node *x)
    {
        Node *t = null;
        for (; x != null; t = x, x = x->fa) splay(x), x->ch[1] = t, up(x);
        return t;
    }
    void cut(Node *x)
    {
        access(x), splay(x);
        x->ch[0]->fa = null, x->ch[0] = null;
        up(x);
    }
    void lk(Node *x, Node *y){ splay(x), x->fa = y; }
    int ask(Node *x, Node *y)
    {
        int res = 0;
        access(x), splay(x);
        res += x->si;
        Node *t = access(y); splay(y);
        res += y->si;
        access(t), splay(t);
        res -= t->si << 1;
        return res;
    }
} lct;
LCT::Node *now;
std::vector<LCT::Node*> fuc;
struct Opt{ int op, pos; LCT::Node *x, *y; };
std::vector<Opt> q;
void make(int l, int r){ live.eb(l, r), fuc.eb(lct._new(1)); }
int main()
{
    scanf("%d %d", &n, &m);
    make(1, n);
    lct.lk(now = lct._new(0), fuc.back());
    while (m--)
    {
        int op, l, r, x;
        scanf("%d %d %d", &op, &l , &r);
        if (op == 0) make(l, r), lct.lk(fuc.back(), now);
        else if (op == 1)
        {
            scanf("%d", &x);
            l = std::max(l, live[x - 1].fi);
            r = std::min(r, live[x - 1].se);
            if (l > r) continue;
            auto t = lct._new(0);
            lct.lk(t, now);
            q.pb({1, l, t, fuc[x - 1]});
            q.pb({1, r + 1, t, now});
            now = t;
        }
        else scanf("%d", &x), q.pb({-m, l, fuc[r - 1], fuc[x - 1]});
    }
    std::sort(q.begin(), q.end(), [&](Opt x, Opt y){ return x.pos == y.pos ? x.op > y.op : x.pos < y.pos; });
    for (int i = 1, j = 0; i <= n; ++i)
        for (; j < q.size() && q[j].pos <= i; ++j)
            if (q[j].op > 0) lct.cut(q[j].x), lct.lk(q[j].x, q[j].y);
            else ans.eb(q[j].op, lct.ask(q[j].x, q[j].y));
    std::sort(ans.begin(), ans.end());
    for (auto t : ans) printf("%d\n", t.se);
    return 0;
}