"Loj 120" 지구 화 시퀀스 - Splay + 오프라인

제목 설명
이것 은 템 플 릿 문제 다.
시퀀스 를 유지 해 야 합 니 다. 다음 동작 을 제공 해 야 합 니 다.

시퀀스 된 t t t 버 전 을 삽입 하여 시퀀스 된 k k k k 항목 으로 만 듭 니 다. 이 수 는 x x x x 입 니 다.

시퀀스 의 t t t 버 전의 k k k 항목 을 삭제 합 니 다.

조회 서열 의 t t t 버 전의 k k k 항.

0 0 번 째 버 전 은 빈 시퀀스 입 니 다.수정 작업 은 수 정 된 버 전에 영향 을 주지 않 고 항상 새로운 버 전이 생 긴 다.
입력 형식
첫 번 째 줄 에는 정수 n n n 이 작업 의 수량 을 표시 합 니 다.
다음 n n 줄 마다 첫 번 째 정수 o p t opt 는 작업 의 유형 을 나타 내 고 그 뒤에 3, 3 개의 정수 t, k, x t, k, x t, k, x t, k, x 또는 22 개의 정수 t, k t, k t, k 는 작업 의 매개 변 수 를 나타 낸다.
출력 형식
모든 조회 작업 출력 줄 의 한 수 에 대해 조회 결 과 를 표시 합 니 다.
분석 하 다.
이것 은 균형 트 리 를 지속 적 으로 유지 할 수 있 는 판자 문제 이지 만, 애석 하 게 도 온라인 을 강제 하지 않 고 오프라인 방법 으로 물 을 건 넜 다.
지속 가능 한 문제 에 대해 서 는 각 버 전이 하나의 버 전 으로 만 바 뀌 었 기 때문에 우리 가 그 버 전 을 새로운 버 전의 아버지 로 본다 면 이것 은 나무 로 볼 수 있다.우 리 는 이 나 무 를 구축 하기 위해 모든 작업 을 오프라인 으로 할 수 있다.그 중의 한 노드 에 대해 이 노드 의 조작 은 그의 서브 트 리 에 만 영향 을 줄 수 있다.그래서 우 리 는 취소 가능 한 데이터 구 조 를 사용 하여 이 노드 의 하위 트 리 에 들 어 갈 때 해당 하 는 작업 을 하고 떠 날 때 이전의 작업 을 취소 할 수 있 습 니 다. 선분 수 분할 처럼 지속 가능 한 효 과 를 얻 을 수 있 습 니 다.
취소 가능 한 데이터 구 조 는 일반 유지보수 구간 의 Splay 를 사용 할 수 있 으 며 블록 체인 도 가능 할 것 같 습 니 다.하위 트 리 에 들 어가 기 전에 해당 동작 을 수정 합 니 다. 가입 은 가입 입 니 다. 삭제 할 때 삭 제 된 노드 의 값 을 기록 한 다음 에 바로 삭제 합 니 다.취소 할 때 이 점 이 추가 작업 이 라면 삭제 하고 삭제 작업 이 라면 추가 하 며 해당 변 의 값 을 취소 합 니 다.
코드 도 간단 해 요.
코드

#include 
#include 
using namespace std;
const int N=600005;
//              ,        ,        
struct Query {int k,id,nxt;}q[N];
struct Edge {int to,nxt;}e[N];
int h[N],cnt;
int op[N],qk[N],qx[N];
int head[N],tot;
void Add_Edge(int x,int y) {
	e[++cnt]=(Edge){y,h[x]};
	h[x]=cnt;
}
void Add_Query(int x,int y,int id) {
	q[++tot]=(Query){y,id,head[x]};
	head[x]=tot;
}
int n,qtot,ans[N],num;
//Splay     
int f[N],c[N][2],v[N];
int sz[N],rt,ntot;
void pushup(int x) {sz[x]=sz[c[x][0]]+sz[c[x][1]]+1;}
void Rotate(int x) {
	int y=f[x],z=f[y];
	int k=c[y][1]==x,w=c[x][k^1];
	if (z) c[z][c[z][1]==y]=x;
	f[y]=x;f[x]=z;if (w) f[w]=y;
	c[x][k^1]=y;c[y][k]=w;
	pushup(y);
	pushup(x);
}
void Splay(int x,int to=0) {
	if (!x) return;
	for (int y,z;z=f[y=f[x]],y!=to;Rotate(x))
		if (z!=to) Rotate((c[y][0]==x)^(c[z][0]==y)?x:y);
	if (!to) rt=x;
}
int Find(int k) {
	int p=rt;
	while (p) {
		if (sz[c[p][0]]+1==k) {
			Splay(p);
			return p;
		}
		if (sz[c[p][0]]>=k) p=c[p][0];
		else k-=sz[c[p][0]]+1,p=c[p][1];
	}
	return 0;
}
void Insert(int k,int val) {
	if (k==1) {
		int x=Find(1);
		Splay(x);ntot++;v[ntot]=val;
		sz[ntot]=1;f[ntot]=x;c[x][0]=ntot;
		if (!x) rt=ntot;
		else pushup(rt);
		return;
	}
	if (k==sz[rt]+1) {
		int x=Find(sz[rt]);
		Splay(x);ntot++;v[ntot]=val;
		sz[ntot]=1;c[x][1]=ntot;f[ntot]=x;
		if (!x) rt=ntot;
		else pushup(x);
		return;
	}
	int x=Find(k-1),y=Find(k);
	Splay(x);Splay(y,x);ntot++;
	v[ntot]=val;sz[ntot]=1;c[c[x][1]][0]=ntot;
	f[ntot]=c[x][1];
	pushup(c[x][1]);
	pushup(x);
}
void Delete(int k) {
	if (k==1) {
		int x=Find(1);
		Splay(x);rt=c[x][1];
		f[c[x][1]]=0;c[x][1]=0;
		return;
	}
	if (k==sz[rt]) {
		int x=Find(sz[rt]);
		Splay(x);rt=c[x][0];
		f[c[x][0]]=0;c[x][0]=0;
		return;
	}
	int x=Find(k),y=Find(k-1);
	Splay(x);
	Splay(y,x);
	f[c[x][0]]=0;
	f[c[x][1]]=c[x][0];
	c[c[x][0]][1]=c[x][1];
	rt=c[x][0];
	pushup(c[x][0]);
}
int Get(int k) {return v[Find(k)];}
//End
void Solve(int x) {
	int dt;
	if (op[x]==1) Insert(qk[x],qx[x]);//    
	else dt=Get(qk[x]), Delete(qk[x]);
	for (int i=head[x];i;i=q[i].nxt)
		ans[q[i].id]=Get(q[i].k);
	for (int i=h[x];i;i=e[i].nxt)
		Solve(e[i].to);
	if (op[x]==1) Delete(qk[x]);//   
	else Insert(qk[x],dt);
}
int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		int opr,t,k,x;
		scanf("%d%d%d",&opr,&t,&k);
		if (opr==1) scanf("%d",&x);
		if (opr==1) {//1,2     ,     ,           
			qtot++;op[qtot]=opr;
			qk[qtot]=k;qx[qtot]=x;
			Add_Edge(t,qtot);
		} else if (opr==2) {
			qtot++;op[qtot]=opr;
			qk[qtot]=k;
			Add_Edge(t,qtot);
		} else if (opr==3) Add_Query(t,k,++num);//3     ,        
	}
	Solve(0);
	for (int i=1;i<=num;i++)
		printf("%d
",ans[i]);
	return 0;
}