지속 가능 한 주제 (3) - 지속 가능 하고 집합 검색 가능

머리말
지속 가능 한 것 을 배우 고 집합 을 찾 으 려 면 먼저 지속 가능 한 배열 을 배 워 야 한다.
L i n k Link Link
지속 가능 한 배열 은 블 로그 의 지속 가능 한 주제 (2) - 지속 가능 한 배열 의 실현 을 자세히 볼 수 있다.
간단 한 소개
지속 가능 하고 집합 을 찾 는 것 은 매우 실 용적 인 데이터 구조 일 것 이다 (예 를 들 어 NOI 2018 Day 1T1 에 그 모습 이 있다).
이 는 주로 지속 가능 한 배열 의 기초 위 에 세 워 졌 다.
L i n k Link Link
주석 트 리 상세 한 내용 은 블 로그 의 지속 가능 한 주제 (1) - 주석 트 리: 지속 가능 한 라인 트 리
순위 에 따라 합병 하 다
지속 가능 하기 때문에 우 리 는 기억 해 야 합 니 다. 지속 가능 하고 집합 을 찾 는 것 은 일반 과 집합 처럼 경 로 를 써 서 압축 할 수 없습니다!
혹시 경로 압축 없 이 T T T 비행 안 하 냐 고 물 어 볼 수도 있 습 니 다.
괜 찮 습 니 다. 경로 압축 이 없습니다. 우 리 는 순위 에 따라 합병 할 수 있 습 니 다. 그의 복잡 도 평균 분담 은 O (l o g n) O (logn) O (logn) O (logn) 입 니 다. 평소에 경로 로 압축 되 었 기 때문에 순위 에 따라 합병 하 는 사람 이 거의 없습니다. (정말 필요 없습니다. 시간 복잡 도 최적화 가 크 지 않 습 니 다) 지금 은 경로 로 압축 할 수 없고 순위 에 따라 합병 하 는 것 이 큰 역할 을 합 니 다.
L i n k Link Link
순위 에 따라 합병 하 는 복잡 도 증명 은 블 로그 계발 식 합병 을 상세 하 게 볼 수 있다.
구체 적 실현
지속 가능 하고 수집 할 수 있 는 것 에 대해 모 르 는 것 이 있다 면 좀 더 생각해 보 는 것 이 좋 습 니 다. 왜냐하면 이것 은 좀 심오 하기 때 문 입 니 다.
다음은 낙 곡 에서 판 자 를 지속 적 으로 찾 을 수 있 는 코드 입 니 다. (코드 가 지속 가능 한 배열 보다 많이 길 었 습 니 다)

#include
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)
#define LL long long
#define swap(x,y) (x^y?(x^=y,y^=x,x^=y):0)
#define tc() (A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++)
#define pc(ch) (pp_<100000?pp[pp_++]=(ch):(fwrite(pp,1,100000,stdout),pp[(pp_=0)++]=(ch)))
#define N 200000 
int pp_=0;char ff[100000],*A=ff,*B=ff,pp[100000];
using namespace std;
int n,Q,tot=0,rt[N+5],a[N+5];
struct Chairman_Tree
{
    int Son[2],fa,level;
}node[N*20];
inline void read(int &x)
{
    x=0;int f=1;char ch;
    while(!isdigit(ch=tc())) f=ch^'-'?1:-1;
    while(x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));
    x*=f;
}
inline void write(int x)
{
    if(x<0) pc('-'),x=-x;
    if(x>9) write(x/10);
    pc(x%10+'0');
}
inline void Build(int &rt,int l,int r)//     ，        fa    ，          
{
	rt=++tot;
	int mid=l+r>>1;
	if(!(l^r)) {node[rt].fa=l;return;}
	Build(node[rt].Son[0],l,mid),Build(node[rt].Son[1],mid+1,r);
}
inline void NewPoint(int &rt,int lst,int l,int r,int x,int fa)//       
{
	rt=++tot;
	int mid=l+r>>1;
	if(!(l^r)) {node[rt].fa=fa,node[rt].level=node[lst].level;return;}//  fa，             level
	node[rt].Son[0]=node[lst].Son[0],node[rt].Son[1]=node[lst].Son[1];
	if(x<=mid) NewPoint(node[rt].Son[0],node[lst].Son[0],l,mid,x,fa);
	else NewPoint(node[rt].Son[1],node[lst].Son[1],mid+1,r,x,fa);
}
inline void Add_level(int rt,int l,int r,int x)//                 
{
	int mid=l+r>>1;
	if(!(l^r)) {++node[rt].level;return;}
	if(x<=mid) Add_level(node[rt].Son[0],l,mid,x);
	else Add_level(node[rt].Son[1],mid+1,r,x);
}
inline int Query(int rt,int l,int r,int x)//  x           
{
	int mid=l+r>>1;
	if(!(l^r)) return rt;
	if(x<=mid) return Query(node[rt].Son[0],l,mid,x);
	else return Query(node[rt].Son[1],mid+1,r,x);
}
inline int getfa(int rt,int x)//  x           
{
	int fa=Query(rt,1,n,x);
	return node[fa].fa^x?getfa(rt,node[fa].fa):fa;//  x               ，   x，    x            ，    getfa()     
}
inline void connect(int v,int x,int y)//   v   x y，          
{
	int fx=getfa(rt[v],x),fy=getfa(rt[v],y);//     v      
	if(!(fx^fy)) return;//      ，     
	if(node[fx].level<node[fy].level) swap(fx,fy);//  x      y    ，   x y
	NewPoint(rt[v],rt[v-1],1,n,node[fy].fa,node[fx].fa);//                       
	if(!(node[fx].level^node[fy].level)) Add_level(rt[v],1,n,node[fx].fa);//          ，               1
}
int main()
{
    register int i;
    for(read(n),read(Q),Build(rt[0],i=1,n);i<=Q;++i)//     ，      
    {
    	int op,x,y;read(op),read(x);
    	if(op^2) read(y),rt[i]=rt[i-1];
    	switch(op)
    	{
    		case 1:connect(i,x,y);break;//        x y
    		case 2:rt[i]=rt[x];break;//             x
    		case 3:pc(getfa(rt[i],x)^getfa(rt[i],y)?'0':'1'),pc('
');break;//      x y     ，  1，    0
		}
    }
    return fwrite(pp,1,pp_,stdout),0;
}