splay求调!!!
查看原帖
splay求调!!!
320449
forest114514楼主2023/8/18 11:30

萌新刚学splay,一直都调不对,大佬们救救萌新吧

code(样例能过 8pts):

//蒟蒻一枚
//【模板】普通平衡树(splay)
#include<bits/stdc++.h>
#define re register
#define il inline
using namespace std;
typedef long long LL;
inline 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<<1)+(x<<3)+(ch&15),ch=getchar();
	return x*f;
}
const int N=2e5+100;
int root,tot;//根的编号,开的点的数量标记 
struct splay_tree{//splay树 
	int fu,son[2],val,cnt,siz;//父节点,左右子节点0/1,点的权值,值出现的数量,子树大小 
}tr[N];
inline void update(int x){//上传子树大小 
	tr[x].siz=tr[tr[x].son[0]].siz+tr[tr[x].son[1]].siz+tr[x].cnt;//左siz+右siz+自cnt 
}
inline void rotate(int x){//单旋 Zag/Zig 
	int y=tr[x].fu,z=tr[y].fu;//操作节点
	int k=(x==tr[y].son[1]);//判断x是y的左/右儿子 
	tr[z].son[y==tr[z].son[1]]=x;//第一步:将x移动为z的子节点
	tr[x].fu=z;
	tr[y].son[k]=tr[x].son[k^1];
	tr[tr[x].son[k^1]].fu=y;//第二步:将x的右/左儿子变为y的左/右儿子
	tr[x].son[k^1]=y;
	tr[y].fu=x;//第三步:将y移动到x的儿子处
	update(y),update(x);//更新子树大小 
}
inline void splay(int x,int goal){//将x旋转到goal的儿子处,特殊的goal==0就旋转为根 
	while(tr[x].fu!=goal){//一直旋转直到到达goal的子节点 
		int y=tr[x].fu;int z=tr[y].fu;
		if(z!=goal) {//双旋 
			((tr[z].son[0]==y)^(tr[y].son[0]==x))?rotate(x):rotate(y);//判断是Zag-Zag/Zig-Zig还是Zig-Zag/Zag-Zig
		}
		rotate(x);//所有旋转的同一操作 
	}
	if(!goal)root=x;//将x记录为根 
}
inline void find(int x){//查找x的位置,若x不存在,则返回x的前驱或后继 
	int u=root;
	if(!u)return;//树空直接跳过 
	while(tr[u].son[x>tr[u].val]&&x!=tr[u].val) //不相等且子树存在
		u=tr[u].son[x>tr[u].val];
	splay(u,0);//将x旋转为根 
}
inline int get_rank(int x){//查找x的排名 
	find(x);//查找x的位置并将x旋转为根 
	return tr[tr[root].son[0]].siz+1+(tr[root].val<x)?1:0;//x的排名=左子树大小+1 (还要处理x不在树中且根是前驱的情况)
}
inline int get_next(int x,int ch){//查询 ch=0:前驱 1:后缀 
	find(x);//先找到x或(它的前驱/后缀(x没出现))
	if(tr[root].val<x&&!ch)return root;//根是前驱且找前驱的情况
	if(tr[root].val>x&&ch) return root;//根是后缀且找后缀的情况
	int u=tr[root].son[ch];
	while(tr[u].son[ch^1])u=tr[u].son[ch^1];
	return u;
} 
inline void Insert(int x){//插入操作 
	int u=root,ff=0;//当前节点与它的父节点
	while(u&&tr[u].val!=x){
		ff=u;
		u=tr[u].son[x>tr[u].val];//走下个点 
	} 
	if(u) tr[u].cnt++;//节点存在则出现次数+1 
	else {//节点不存在则新开点 
		u=++tot; 
		if(ff) tr[ff].son[x>tr[ff].val]=u;
		tr[u].siz=tr[u].cnt=1;
		tr[u].val=x;
		tr[u].fu=ff;
	}
	splay(u,0);
}
inline void Delete(int x){//删除操作 
	int lst=get_next(x,0),nxt=get_next(x,1);//找到x的前驱和后缀
	splay(lst,0),splay(nxt,lst);//将前驱移到根,后驱变为前驱右儿子,这样只有x是后驱的左儿子,删了也不影响其他的点
	int del=tr[nxt].son[0];//要删掉的x所在点
//	if(tr[del].val!=x)return;
	if(tr[del].cnt>1){
		tr[del].cnt--;
		splay(del,0);
	} 
	else tr[nxt].son[0]=0;//丢掉就行了 
}
inline int get_kth(int k){
	int u=root;
	if(tr[u].siz<k)return 0;//没有k个数
	while(1){
		if(k>tr[tr[u].son[0]].siz+tr[u].cnt){//k比左子树加上当前节点的数的数量还大,走右节点 
			k-=tr[tr[u].son[0]].siz+tr[u].cnt;
			u=tr[u].son[1];
		}
		else{
			if(tr[tr[u].son[0]].siz>=k){//左儿子大小足够 
				k-=tr[u].cnt;
				u=tr[u].son[0];
			} 
			else return tr[u].val;//否则返回当前节点的值 
		} 
	} 
}
int main(){
	//ios::sync_with_stdio(false);
	//cin.tie(0);cout.tie(0);
	int T=read();
//	Insert(0x3f3f3f3f),Insert(-0x3f3f3f);
	while(T--){
		int opt=read(),x=read();
		switch(opt){//普通的判断操作 
			case 1:{
				Insert(x);//插入 
				break;
			}
			case 2:{
				Delete(x);//
				break;
			}
			case 3:{
				printf("%d\n",get_rank(x));
				break;
			}
			case 4:{
				printf("%d\n",get_kth(x));
				break;
			}
			case 5:{
//				Insert(x);
				printf("%d\n",tr[get_next(x,0)].val);
//				Delete(x);
				break;
			}
			case 6:{
//				Insert(x);
				printf("%d\n",tr[get_next(x,1)].val);
//				Delete(x);
				break;
			}
		}
	}
	return 0;
}

2023/8/18 11:30
加载中...