트 리 데이터 구조 - LCT
개술
LCT 는 강력 한 트 리 데이터 구조 로 다음 작업 을 지원 합 니 다.
기본 개념
LCT 는 나무의 실 사슬 을 나 누 는 것 으로 모든 변 을 실 변 과 허 변 으로 나 누 는 것 이다.
중 사슬 분할 과 비슷 하 다. 각 점 에서 자 노드 에 연 결 된 실 사슬 은 기껏해야 하나 밖 에 없 는데 이 실 변 을 연결 하 는 아들 을 실 아들 이 라 고 부른다.
일부 실제 연결 점 으로 구 성 된 체인 을 실제 체인 이 라 고 하 는데 실제 체인 간 에 공통점 이 없다 는 것 을 쉽게 발견 할 수 있다.
주의해 야 할 것 은 실제 가장자리 에 없 는 점 (일부 잎 노드) 도 실제 가장자리 가 없 는 실제 체인 으로 여 긴 다 는 것 이다.
그래서 실제 체인 사 이 는 반드시 허 변 으로 연 결 된 것 이다.
동적 삭제 와 관련 된 작업 을 하려 면 splay 를 사용 하여 실제 체인 을 유지 합 니 다. splay 는 LCT 의 보조 트 리 입 니 다.
이 곳 splay 의 깊이 는 중간 순서에 따라 엄 격 히 증가 합 니 다.
splay 로 유지 하기 때문에 LCT 의 실제 변 화 는 동적 이 고 바 꿀 수 있 습 니 다.
핵심 조작
access (x): x 에서 뿌리 노드 까지 의 모든 변 을 실제 변 으로 하고 x 는 실제 아들 이 없다.
이 건 플래시hu 의 블 로그
조금 만 말씀 드 리 겠 습 니 다. 매번 조작 할 때마다 현재 연결 할 점 splay 를 현재 splay 의 뿌리 로 옮 깁 니 다. splay 의 깊이 가 중간 순서에 따라 점점 증가 하기 때문에 이때 뿌리 오른쪽 아들 은 반드시 전에 연 결 된 실제 체인 입 니 다. 제거 해 야 합 니 다.
그래서 이전의 점 을 현재 뿌리 의 오른쪽 아들 에 게 연결 하면 된다.
이때 일부 \ (fa, son, isroot \) 와 같은 정보 가 바 뀌 었 으 니 주의해 야 합 니 다 \ (push \) \(up\)
void access(int x){
for(int y=0;x;y=x,x=fa[x]){ //y ，x
splay(x); ch[x][1]=y;
push_up(x);
}
}기타 조작
void pushr(int x){
swap(ch[x][0],ch[x][1]);
r[x]^=1;
}
void makeroot(int x){
access(x); splay(x);
pushr(x);
}int findroot(int x){
access(x);splay(x);
while(c[x][0]) push_down(x),x=ch[x][0];// ， push_down x ，
splay(x);// splay
return 0;
}void spilt(int x,int y){
makeroot(x);access(y);
splay(y);
}int link(int x,int y){
makeroot(x);
if(findroot(y)==x) return 0;
fa[x]=y; // x y
return 1;
}void link(int x,int y){
makeroot(x);
fa[x]=y;
}void cut(int x,int y){
split(x,y);
fa[x]=ch[y][0]=0;
}int cut(int x,int y){
makeroot(x);
if(findroot(y)!=x||fa[y]!=x||ch[y][0]) return 0;
fa[y]=ch[x][1]=0;
push_up(x);
return 1;
}int nroot(int x){
return (ch[fa[x]][1]==x||ch[fa[x]][0]==x);
}#include
#include
#include
#include
using namespace std;
#define reg register int
#define il inline
#define ls ch[x][0]
#define rs ch[x][1]
int read(){
int x=0,pos=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') pos=0;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return pos?x:-x;
}
const int N = 400025;
int fa[N],ch[N][2],v[N],s[N],st[N],r[N];
il int nroot(int x){
return ch[fa[x]][1]==x||ch[fa[x]][0]==x;
}
il int get(int x){
return ch[fa[x]][1]==x;
}
il void push_up(int x){
s[x]=v[x]^s[ls]^s[rs];
}
il void pushr(int x){
swap(ls,rs);r[x]^=1;
}
il void push_down(int x){
if(r[x]){
if(ls) pushr(ls);
if(rs) pushr(rs);
r[x]=0;
}
}
il void rotate(int x){
int f=fa[x],g=fa[f],kx=get(x),kf=get(f);
if(nroot(f)) ch[g][kf]=x;
fa[x]=g;
/*if(ch[x][kx^1])*/ fa[ch[x][kx^1]]=f;
ch[f][kx]=ch[x][kx^1];
fa[f]=x;ch[x][kx^1]=f;
push_up(f);push_up(x);
}
il void push(int x){
if(nroot(x)) push(fa[x]);
push_down(x);
}
il void splay(int x){
int f,g;
push(x);//fuctional stack
while(nroot(x)){
f=fa[x],g=fa[f];
if(nroot(f)){
rotate(get(x)==get(f)?f:x);
}
rotate(x);
}
}
il void access(int x){
for(reg y=0;x;y=x,x=fa[x]){
splay(x);rs=y;push_up(x);
}
}
il void makeroot(int x){
access(x);splay(x);pushr(x);
}
il void spilt(int x,int y){
makeroot(x);
access(y);splay(y);
}
il int findroot(int x){
access(x);splay(x);
while(ls) x=ls;
splay(x);
return x;
}
il void link(int x,int y){
makeroot(x);
if(findroot(y)!=x) fa[x]=y;
}
il void cut(int x,int y){
makeroot(x);
if(findroot(y)==x&&fa[y]==x&&!ch[y][0]){
fa[y]=ch[x][1]=0;
push_up(x);
}
}
int n,m;
int main(){
n=read();m=read();
for(reg i=1;i<=n;i++){
v[i]=read();
}
for(reg i=1;i<=m;++i){
int opt=read(),x=read(),y=read();
if(opt==0){
spilt(x,y);printf("%d
",s[y]);
}else if(opt==1){
link(x,y);
}else if(opt==2) cut(x,y);
else splay(x),v[x]=y;
}
return 0;
} 나중에 본인 이 만 든 LCT 문 제 를 고 칠 수도 있어 요.
본 고 를 창작 하 는 과정 에서 다음 과 같은 글 을 참고 했다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
