Bzoj 3673: 可持久化并查集 by zky(主席树+启发式合并)

3673: 可持久化并查集 by zky

Time Limit: 5 Sec Memory Limit: 128 MB

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

/*

可持久化线段树+启发式合并.

可持久化线段树维护当前状态下集合的关系和秩的信息.

所谓的秩就是以该元素为代表元的所有元素中的最大深度.

然后按秩合并的目的是为了降常.

每个叶节点维护一颗线段树

合并的时候在权值线段树的子节点加一个数,

相当于连了一条边 表示有关系存在.

要先查询要将合并两个元素的父亲所在位置.

显然只有在两个集合秩相同时才更新秩.

*/

#include<iostream>

#include<cstdio>

#define MAXN 20001

using namespace std;

int n,m,tot,root[MAXN],s[MAXN];

struct data{int lc,rc,deep,x;}tree[MAXN*20];

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

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

{

    k=++tot;

    if(l==r){tree[k].x=l;return ;}

    int mid=(l+r)>>1;

    build(tree[k].lc,l,mid);

    build(tree[k].rc,mid+1,r);

    return ;

}

int query(int k,int l,int r,int x)

{

    if(l==r) return k;

    int mid=(l+r)>>1;

    if(x<=mid) return query(tree[k].lc,l,mid,x);

    else return query(tree[k].rc,mid+1,r,x);

}

int find(int root,int x)

{

    int p=query(root,1,n,x);

    if(x==tree[p].x) return p;

    else return find(root,tree[p].x);

}

void change(int &k,int last,int l,int r,int x,int y)

{

    k=++tot;tree[k].lc=tree[last].lc,tree[k].rc=tree[last].rc;

    if(l==r) {

        tree[k].x=y;tree[k].deep=tree[last].deep;

        return ;

    }

    int mid=(l+r)>>1;

    if(x<=mid) change(tree[k].lc,tree[last].lc,l,mid,x,y);

    else change(tree[k].rc,tree[last].rc,mid+1,r,x,y);

    return ;

}

void updata(int k,int l,int r,int x)

{

    if(l==r){tree[k].deep++;return ;}

    int mid=(l+r)>>1;

    if(x<=mid) updata(tree[k].lc,l,mid,x);

    else updata(tree[k].rc,mid+1,r,x);

    return ;

}

void union_s(int l1,int l2,int i)

{

    if(tree[l1].deep>tree[l2].deep) swap(l1,l2);

    change(root[i],root[i-1],1,n,tree[l1].x,tree[l2].x);

    if(tree[l1].deep==tree[l2].deep) updata(root[i],1,n,tree[l2].x);

    return ;

}

int main()

{

    int x,y,z,l1,l2;

    n=read(),m=read();

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

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

    {

        z=read();

        if(z==1)

        {

            x=read(),y=read();

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

            l1=find(root[i],x),l2=find(root[i],y);

            if(tree[l1].x!=tree[l2].x) union_s(l1,l2,i);

        }

        else if(z==2) x=read(),root[i]=root[x];

        else {

            x=read(),y=read();

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

            l1=find(root[i],x),l2=find(root[i],y);

            if(l1==l2) printf("1\n");

            else printf("0\n");

        }

    }

    return 0;

}

巴特西

Bzoj 3673: 可持久化并查集 by zky(主席树+启发式合并)

最新文章

热门文章