BZOJ 3674 可持久化并查集加强版（主席树变形）

3673: 可持久化并查集 by zky

Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 2515 Solved: 1107
[Submit][Status][Discuss]

Description

n个集合 m个操作
操作：
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0

0<n,m<=2*10^4

Input

Output

Sample Input

5 6
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2

Sample Output

1
0
1

HINT

Source

出题人大SB

题目链接：BZOJ 3674

原来并查集也是可以可持久化的，其思想应该是在于用可持久化数据结构来维护一个前缀记录，由于普通的并查集一开始每一个节点的祖先都是本身，因此要多一个建树的操作，把所有的叶子节点的祖先都处理好，然后这题是并查集，并不需要差分的思想，也就是说更新或者查询只需要用到一个root点，其他的做法跟普通的并查集差不多，详细的可以看黄大牛的博客：http://hzwer.com/3997.html。

代码：

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);

typedef pair<int, int> pii;

typedef long long LL;

const double PI = acos(-1.0);

const int N = 2e5 + 7;

struct seg

{

    int lson, rson;

    int pre;

};

seg T[N * 20];

int root[N], tot;

int n;

void init()

{

    CLR(root, 0);

    tot = 0;

}

void build(int &cur, int l, int r)

{

    cur = ++tot;

    T[cur].lson = T[cur].rson = 0;

    if (l == r)

        T[cur].pre = l;

    else

    {

        int mid = MID(l, r);

        build(T[cur].lson, l, mid);

        build(T[cur].rson, mid + 1, r);

    }

}

void update(int &cur, int ori, int l, int r, int pos, int pre)

{

    cur = ++tot;

    T[cur] = T[ori];

    if (l == r)

    {

        T[cur].pre = pre;

        return ;

    }

    else

    {

        int mid = MID(l, r);

        if (pos <= mid)

            update(T[cur].lson, T[ori].lson, l, mid, pos, pre);

        else

            update(T[cur].rson, T[ori].rson, mid + 1, r, pos, pre);

    }

}

int query(int k, int l, int r, int pos) //返回子节点位置

{

    if (l == r)

        return k;

    else

    {

        int mid = MID(l, r);

        if (pos <= mid)

            return query(T[k].lson, l, mid, pos);

        else

            return query(T[k].rson, mid + 1, r, pos);

    }

}

int Find(int k, int pre)

{

    int idx = query(k, 1, n, pre);

    if (pre == T[idx].pre)

        return pre;

    else

        return Find(k, T[idx].pre);

}

int main(void)

{

    int m, i, a, b, k, ops;

    while (~scanf("%d%d", &n, &m))

    {

        init();

        int ans = 0;

        build(root[0], 1, n);

        for (i = 1; i <= m; ++i)

        {

            scanf("%d", &ops);

            if (ops == 1)

            {

                scanf("%d%d", &a, &b);

                a ^= ans, b ^= ans;

                root[i] = root[i - 1];

                int fa = Find(root[i], a);

                int fb = Find(root[i], b);

                if (fa != fb)

                    update(root[i], root[i - 1], 1, n, fb, fa);

            }

            else if (ops == 2)

            {

                scanf("%d", &k);

                k ^= ans;

                root[i] = root[k];

            }

            else if (ops == 3)

            {

                scanf("%d%d", &a, &b);

                a ^= ans, b ^= ans;

                root[i] = root[i - 1];

                int fa = Find(root[i], a);

                int fb = Find(root[i], b);

                printf("%d\n", ans = (fa == fb));

            }

        }

    }

    return 0;

}

巴特西