P3402 可持久化并查集题解

· · 题解

P3402 题解

题目传送门 P3402

题目大意

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

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

题目分析

首先我们来学一一个非常方便，简洁，且高端的东西。

它就是 rope 。

什么是 rope ？它可以当做可持久化数据结构使用，其内部构造则是一个块状链表。

调用 rope 的时候需要头文件 #include<ext/rope>

当然，以后你还会学到别的和 rope 一样的操作，如果你不想背那么多头文件的话，可以使用 #include <bits/extc++.h>

注：#include<bits/stdc++.h> 头文件并不包含 #include <bits/extc++.h> 头文件。

仅仅这样是没有办法定义 rope 的。

我们还需要调用命名空间， using namespace __gnu_cxx;

注：__gnu_cxx 是一个新的空间，同头文件，它也是脱离了 namespace std 库的存在。

当然，我们也可以通过 __gnu_cxx::rope 来定义。

rope 的声明使用方式如下：

rope<int> arr;

struct SegmentTree
{
   int l, r;
   int id;
};
rope<node> t;

crope ch;//即 rope char;

在这道题中，我们需要了解 rope 的一个很强的函数功能 ： replace

replace(p,x) : 从 rope 的下标 p 开始替换成数组 x ，x 的长度为从 p 开始替换的位数，如果 p 后的位数不够就补足。

这里插一句，rope 本身就是一个可持久化数组。

那么放到这个题呢？

直接写正常的并查集模板就行了啊！

实际写法开一堆数组，暴力维护即可，相同的做法也可以在 P6166 中尝试。

代码

此题数据范围略大，需要吸氧

#include <bits/stdc++.h>
#include <ext/rope>

//#define int long long
#define endl '\n'
#define rint register unsigned

using namespace __gnu_cxx;
using namespace std;

#define IN stdin->_IO_read_ptr < stdin->_IO_read_end ? *stdin->_IO_read_ptr++ : __uflow(stdin)
#define OUT(_ch) stdout->_IO_write_ptr < stdout->_IO_write_end ? *stdout->_IO_write_ptr++ = _ch : __overflow(stdout, _ch)

const int N = 2e5 + 5;

unsigned f[N];
unsigned r[N];

void read(unsigned &x)
{
    x = 0;
    char ch = IN;
    while (ch < 47)
        ch = IN;
    while (ch > 47)
        x = (x << 1) + (x << 3) + (ch & 15), ch = IN;
}

unsigned find(rope<unsigned> &fa, unsigned &i)
{
    unsigned f = fa[i];
    return f == i ? i : find(fa, f);
}

void merge(rope<unsigned> &fa, unsigned &a, unsigned &b)
{
    a = find(fa, a);
    b = find(fa, b);

    if (a == b)
    {
        return ;
    }
    if (r[a] > r[b])
    {
        fa.replace(b, a);       
    }
    else
    {
        if (r[a] == r[b])
        {
            r[b]++;         
        }
        fa.replace(a, b);
    }
}

signed main()
{
    unsigned n, m, op, a, b;
    read(n);
    read(m);
    rope<unsigned> fa[m + 1];

    for (rint i = 1; i <= n; i++)
    {
        f[i] = i;
    }    

    f[0] = 1;
    fa[0] = rope<unsigned>(f);

    for (rint i = 1; i <= m; i++)
    {
        read(op);

        switch (op)
        {
        case 1:
            fa[i] = fa[i - 1];
            read(a);
            read(b);
            merge(fa[i], a, b);
            break;
        case 2:
            read(a);
            fa[i] = fa[a];
            break;
        default:
            fa[i] = fa[i - 1];
            read(a); 
            read(b);
            OUT(find(fa[i], a) == find(fa[i], b) ? '1' : '0');
            puts("");
        }
    }

    return 0;
}

update （2022.8.21） ： 感谢 @东灯 提供的快读让此代码在吸氧后无压力通过此题（不吸氧可得 78pts）