题目描述

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

0

输入格式

输出格式

输入样例

5 6

1 1 2

3 1 2

2 0

3 1 2

2 1

3 1 2

输出样例

1

0

1

题解

这道题要维护可持续化并查集，由于并查集是由数组实现的，所以实质是维护并查集的pre数组
路径压缩怎么办？实际上可以按轶合并，轶指最深的深度
每次合并集合时，将轶小的并到轶大的，当二者相等，被并的轶+1，即最大深度+1
这样子维护的并查集近似于完全二叉树，可以做到查询均摊O(logn)

由于没怎么写过可持续化数组，这里讲一讲：
可持续化数组，实际上就是可持续化线段树。可以看做废掉了中间节点的主席树，每次修改和查询都一样，无论是空间还是时间都是O(logn)

我们先开一个0版本线段树，每个叶子节点有一个值，表示对应位置的数组的值

每次修改，加一个版本的根，然后让新版本的树沿着上一版本创建。有修改的那一条路径新开节点，剩余的子树指向原版本【因为本来就一样】

每次询问，只需找到对应版本的根，往叶子查找即可

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u]; k != -1; k = ed[k].nxt)

using namespace std;

const int maxn = 20005,maxm = 2000005,INF = 1000000000;

inline int RD(){

    int out = 0,flag = 1; char c = getchar();

    while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

    while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}

    return out * flag;

}

int N,M,siz = 0,rt[maxn],ri = 0;

struct node{int ls,rs,fa,dep;}e[maxm];

void build(int& u,int l,int r){

    u = ++siz;

    if (l == r){e[u].fa = l; return;}

    int mid = l + r >> 1;

    build(e[u].ls,l,mid);

    build(e[u].rs,mid + 1,r);

}

int Query(int u,int l,int r,int pos){

    if (l == r) return u;

    int mid = l + r >> 1;

    if (mid >= pos) return Query(e[u].ls,l,mid,pos);

    else return Query(e[u].rs,mid + 1,r,pos);

}

void modify(int& u,int pre,int l,int r,int pos,int val){

    e[u = ++siz] = e[pre];

    if (l == r) {e[u].fa = val; return;}

    int mid = l + r >> 1;

    if (mid >= pos) modify(e[u].ls,e[pre].ls,l,mid,pos,val);

    else modify(e[u].rs,e[pre].rs,mid + 1,r,pos,val);

}

void add(int u,int l,int r,int pos){

    if (l == r) {e[u].dep++; return;}

    int mid = l + r >> 1;

    if (mid >= pos) add(e[u].ls,l,mid,pos);

    else add(e[u].rs,mid + 1,r,pos);

}

int find(int R,int u){

    int p = Query(R,1,N,u);

    if (e[p].fa == u) return p;

    return find(R,e[p].fa);

}

int main(){

    N = RD(); M = RD(); int cmd,a,b,fa,fb;

    build(rt[0],1,N);

    REP(i,M){

        cmd = RD(); a = RD(); ri++;

        if (cmd == 1){

            b = RD(); rt[i] = rt[i - 1];

            fa = find(rt[i],a); fb = find(rt[i],b);

            if (e[fa].fa != e[fb].fa){

                if (e[fa].dep > e[fb].dep) swap(fa,fb);

                modify(rt[ri],rt[ri - 1],1,N,e[fa].fa,e[fb].fa);

                if (e[fa].dep == e[fb].dep) add(rt[ri],1,N,e[fb].fa);

            }

        }else if (cmd == 2){

            rt[ri] = rt[a];

        }else {

            b = RD(); rt[ri] = rt[ri - 1];

            fa = find(rt[ri],a); fb = find(rt[ri],b);

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

        }

    }

    return 0;

}

题目描述

Description：
自从zkysb出了可持久化并查集后……
hzwer:乱写能AC，暴力踩标程
KuribohG：我不路径压缩就过了！
ndsf：暴力就可以轻松虐！
zky:……

n个集合 m个操作
操作：
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0
请注意本题采用强制在线,所给的a,b,k均经过加密,加密方法为x = x xor lastans,lastans的初始值为0
0

输入格式

输出格式

输入样例

5 6

1 1 2

3 1 2

2 1

3 0 3

2 1

3 1 2

输出样例

1

0

1

题解

实际是一样的，O(nlog2n)的复杂度怎么卡得掉

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u]; k != -1; k = ed[k].nxt)

using namespace std;

const int maxn = 200005,maxm = 10000005,INF = 1000000000;

inline int RD(){

    int out = 0,flag = 1; char c = getchar();

    while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

    while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}

    return out * flag;

}

int N,M,siz = 0,rt[maxn],ri = 0;

struct node{int ls,rs,v,dep;}e[maxm];

void build(int& u,int l,int r){

    if (!u) u = ++siz;

    if (l == r){e[u].v = l; return;}

    int mid = l + r >> 1;

    build(e[u].ls,l,mid);

    build(e[u].rs,mid + 1,r);

}

int Query(int u,int l,int r,int pos){

    if (l == r) return u;

    int mid = l + r >> 1;

    if (mid >= pos) return Query(e[u].ls,l,mid,pos);

    else return Query(e[u].rs,mid + 1,r,pos);

}

void modify(int& u,int pre,int l,int r,int pos,int val){

    u = ++siz;

    if (l == r) {e[u].v = val; e[u].dep = e[pre].dep; return;}

    e[u].ls = e[pre].ls; e[u].rs = e[pre].rs;

    int mid = l + r >> 1;

    if (mid >= pos) modify(e[u].ls,e[pre].ls,l,mid,pos,val);

    else modify(e[u].rs,e[pre].rs,mid + 1,r,pos,val);

}

void add(int u,int l,int r,int pos){

    if (l == r) {e[u].dep++; return;}

    int mid = l + r >> 1;

    if (mid >= pos) add(e[u].ls,l,mid,pos);

    else add(e[u].rs,mid + 1,r,pos);

}

int find(int R,int u){

    int p = Query(R,1,N,u);

    if (e[p].v == u) return p;

    return find(R,e[p].v);

}

int main(){

    N = RD(); M = RD(); int cmd,a,b,p,q,last = 0;

    build(rt[0],1,N);

    REP(i,M){

        cmd = RD(); a = RD() ^ last; ri++;

        if (cmd == 1){

            b = RD() ^ last; rt[i] = rt[i - 1];

            p = find(rt[i],a); q = find(rt[i],b);

            if (e[p].v != e[q].v){

                if (e[p].dep > e[q].dep) swap(p,q);

                modify(rt[ri],rt[ri - 1],1,N,e[p].v,e[q].v);

                if (e[p].dep == e[q].dep) add(rt[ri],1,N,e[q].v);

            }

        }else if (cmd == 2){

            rt[ri] = rt[a];

        }else {

            b = RD() ^ last; rt[ri] = rt[ri - 1];

            p = find(rt[ri],a); q = find(rt[ri],b);

            if (e[p].v == e[q].v) last = 1;

            else last = 0;

            printf("%d\n",last);

        }

    }

    return 0;

}