P3402-可持久化并查集

ybw051114

2020-05-01 约 1391 字预计阅读 3 分钟次阅读

P3402-可持久化并查集

题目:

题目描述:

给定 $n$ 个集合，第 $i$ 个集合内初始状态下只有一个数，为 $i$。

有 $m$ 次操作。操作分为 $3$ 种：

1 a b 合并 $a,b$ 所在集合；
2 k 回到第 $k$ 次操作（执行三种操作中的任意一种都记为一次操作）之后的状态；
3 a b 询问 $a,b$ 是否属于同一集合，如果是则输出 $1$ ，否则输出 $0$。

输入格式:

第一行两个整数，$n,m$。

接下来 $m$ 行，每行先输入一个数 $opt$。若 $opt=2$ 则再输入一个整数 $k$，否则再输入两个整数 $a,b$，描述一次操作。

输出格式:

对每个操作 $3$，输出一行一个整数表示答案。

样例:

样例输入 1:

样例输出 1:

思路:

首先明确一点，本题考得不是并查集，而是可持久化跟并查集没啥关系。

而且在这道题中用不带路径压缩的并查集（欢迎推翻这个 flag）

然后我们看到‘历史版本’，自然而然想到可持久化数据结构–主席树。

那我们用主席树干什么呢？

维护每一个版本中每一个点的父亲，也就是我们熟悉的并查集中的 fa[x]

再然后，因为我们用用不带路径压缩的并查集

所以对于每一次合并只会改一个点的父亲

所以一个版本的相对于上一个版本只会改一个点

所以有很多地方可以共用

这也证明了为什么要用可持久化数据结构（可持久化数据结构就是共用一些点来达到节省空间的效果）

明白了主席树的作用之后，并查集中 find_fa 的思路大体上就出来了：

1.在主席树上，查询某一个版本中一个点的父亲

2.它成为它的父亲

3.重复步骤 1,直到找到 root

但是我们发现，如果并查集退化成一条链，find_fa 复杂度会很高（虽然这题很水，暴力都可以过去）

又不能路径压缩（不然就不能一次修改一个点，就不好搞可持久化了）（欢迎推翻这个 flag）

于是我们可以在 Union 上下一点功夫使得它不会变成一条链

想到合并方法–启发式合并

怎么启发？

把最大深度小的往最大深度大的上并

于是最大深度大的深度不会增加

而是最大深度小的增加深度 这样不久巧妙地保证了深度均衡吗？

好了，基本上是讲完了实在不懂可以看着代码理解代码在下面，有注释

实现:

  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
#include <bits/stdc++.h>
#include "ybwhead/ios.h"
int n, m;
const int maxn = 2e5 + 10;
int tot;
int root[maxn];
struct T
{
    int l, r, f, d;
} t[maxn << 5];

inline int build(int l, int r)
{
    int p = ++tot;
    if (l == r)
    {
        t[p].f = l;
        t[p].d = 1;
        return p;
    }
    int mid = (l + r) >> 1;
    t[p].l = build(l, mid);
    t[p].r = build(mid + 1, r);
    return p;
}

inline int ask(int p, int l, int r, int x)
{
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (x <= mid)
        {
            r = mid;
            p = t[p].l;
        }
        else
        {
            l = mid + 1;
            p = t[p].r;
        }
    }
    return p;
}

inline int add(int pre, int l, int r, int x)
{
    int p = ++tot;
    if (l == r)
    {
        t[p].f = x;
        t[p].d = t[pre].d + 1;
        return p;
    }
    t[p].l = t[pre].l;
    t[p].r = t[pre].r;
    int mid = (l + r) >> 1;
    if (x <= mid)
        t[p].l = add(t[pre].l, l, mid, x);
    else
        t[p].r = add(t[pre].r, mid + 1, r, x);
    return p;
}

inline int add(int pre, int l, int r, int s, int f)
{
    int p = ++tot;
    if (l == r)
    {
        t[p].f = f;
        t[p].d = t[pre].d;
        return p;
    }
    t[p].l = t[pre].l;
    t[p].r = t[pre].r;
    int mid = (l + r) >> 1;
    if (s <= mid)
        t[p].l = add(t[pre].l, l, mid, s, f);
    else
        t[p].r = add(t[pre].r, mid + 1, r, s, f);
    return p;
}

int gf(int rt, int x)
{
    int k = ask(rt, 1, n, x);
    if (t[k].f == x)
        return k;
    return gf(rt, t[k].f);
}
int main()
{
    yin >> n >> m;
    root[0] = build(1, n);
    int ans = 0, o, x, y;
    for (int i = 1; i <= m; i++)
    {
        root[i] = root[i - 1];
        yin >> o;
        if (o == 1)
        {
            yin >> x >> y;
            int rx = gf(root[i], x);
            int ry = gf(root[i], y);
            if (t[rx].f == t[ry].f)
                continue;
            if (t[rx].d > t[ry].d)
                swap(rx, ry);
            root[i] = add(root[i - 1], 1, n, t[rx].f, t[ry].f);
            if (t[rx].d == t[ry].d)
                root[i] = add(root[i], 1, n, t[ry].f);
        }
        else if (o == 2)
        {
            yin >> x;
            root[i] = root[x];
        }
        else
        {
            yin >> x >> y;
            int rx = gf(root[i], x);
            int ry = gf(root[i], y);
            yout << (ans = rx == ry) << endl;
        }
    }
}

目录

P3402-可持久化并查集

P3402-可持久化并查集

题目:

题目描述:

输入格式:

输出格式:

样例:

样例输入 1:

样例输出 1:

思路:

实现: