BZOJ3673&BZOJ3674 可持久化并查集及加强版

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< n,m<=2*10^5

非加强版(不用强制在线)

加强版

Solution

反正我敲的是可持久化并查集，加不加强对我没影响==

首先讲思路。

没有看过可持久化并查集的时候真心不知该咋搞。一开始想分块，然而分块好像会炸内存。。

于是去看了下hzwer的博客，听说可持久化并查集可以用主席树搞。

正好前阵子学了主席树(然而已经不会敲了==)，于是非常开心的重新想。

想了半天不知道该维护什么。

然后去问ShinFeb大神，他说，维护“秩”啊==

于是又去查“秩”是什么

结果发现“秩”是按“秩”合并并查集的东西。

于是又去查按“秩”合并并查集是什么

结果发现按“秩”合并并查集就是启发式合并。。

名字真多

然后看了半天发现这个启发式合并不是我印象中的启发式合并！！！

有点陶醉。。原来自己理解的启发式合并那么……

概念

按秩合并并查集不用路径压缩，总的路径是logn的复杂度。

合并时先getfa

然后每次合并前check一下fa的“秩”

“秩”即一个集合树中最远的点到根的点的距离。

如果“秩”不同那么把“秩”小的接到秩大的下面

如果“秩”相同那么随便选一个当根，另一个接上去，然后整棵集合树的“秩”+1

按秩合并并查集有以下两个优点(自己感觉的，可能比较片面)

1）不会爆栈

一共就logn层况且可以不用递归。

2）方便复原

不想路径压缩那样一下子连一坨边，而是一条一条连边，自然好复原

处于原因2，这道题我们用按秩合并并查集。

可以发现每次合并集合只有一个点的fa变了，至多有一个秩变了(我们只维护集合树中树根的秩，其他点的秩没用)

我们可以用主席树来维护各个版本的fa以及d

然后就没了==

Code

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int M=+;
const int N=M*;
inline void rd(int &a){
    a=;char c;
    while(c=getchar(),!isdigit(c));
    do a=a*+(c^);
        while(c=getchar(),isdigit(c));
}
int fa[N],d[N],ls[N],rs[N],tot=,rt[M],n,m;
void build(int &tid,int l=,int r=n){
    tid=++tot;
    if(l==r){fa[tid]=l;return;}
    int mid=l+r>>;
    build(ls[tid],l,mid);
    build(rs[tid],mid+,r);
}
void modify(int ot,int &tid,int l,int r,const int &x,const int &a,const int &dep){
    tid=++tot;
    ls[tid]=ls[ot],rs[tid]=rs[ot];
    if(l==r){
        fa[tid]=a;
        if(~dep)d[tid]=dep;
        return;
    }
    int mid=l+r>>;
    if(x<=mid)modify(ls[ot],ls[tid],l,mid,x,a,dep);
    else modify(rs[ot],rs[tid],mid+,r,x,a,dep);
}
int query(int tid,const int &x,int l,int r,const bool &f){//query fa 
    if(l==r)return f?d[tid]:fa[tid];
    int mid=l+r>>;
    if(x<=mid)return query(ls[tid],x,l,mid,f);
    return query(rs[tid],x,mid+,r,f);
}
int find(const int &rt,int x){
    int v=query(rt,x,,n,);
    return v==x?x:find(rt,v);
}
int main(){
    cin>>n>>m;
    build(rt[],,n);
    for(int a,b,c,lastans=,i=;i<=m;++i){
        rd(a),rd(b);
        b^=lastans;
        if(a==){
            rd(c);
            c^=lastans;
            rt[i]=rt[i-];
            //0:fa 1:d
            int f1=find(rt[i],b),f2=find(rt[i],c);
            int d1=query(rt[i],f1,,n,),d2=query(rt[i],f2,,n,);
            if(d1<d2)swap(b,c),swap(f1,f2),swap(d1,d2);//d2>d1
            //fa[f2]=f1
            if(d1==d2)modify(rt[i-],rt[i],,n,f2,f1,d1+);
            else modify(rt[i-],rt[i],,n,f2,f1,-);
            //union
        }
        if(a==)rt[i]=rt[b];//return
        if(a==){//check
            rd(c);
            c^=lastans;
            rt[i]=rt[i-];
            int f1=find(rt[i],b),f2=find(rt[i],c);
            if(f1==f2)puts("1"),lastans=;
            else puts("0"),lastans=;
        }
    }
    return ;
}