Luogu P3369 【模闆】普通平衡樹

啊 splay啊

代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>

//左兒子一定比我小 右兒子一定比我大 
/* 		  * <----0
          | 
          * <----rt 
       /   \
      *    *
     / \  / \
    *  * *   *   這是一棵樹 
*/  

struct nod1{int ch[2],c,fa,size,cnt;}tr[110010];
//ch[0]是左兒子編号 ch[1]是右兒子比那好 
//c是節點數值 fa是節點爸爸 size是以節點為根子樹大小  
//cnt是和節點數值一樣的數的個數 
int n,rt,tot;
//n是操作數 rt是根 tot是整個數的節點個數，添加新節點時用到 

void update(int x)//更新維護 此處x是編号 
{
	tr[x].size=tr[tr[x].ch[0]].size+tr[x].cnt+tr[tr[x].ch[1]].size;
	//x子樹大小=x左子樹+x右子樹+x節點相同數個數 
	return ;
}//ok

int findip(int x)//找x數值的節點編号 此處x是數值 
{
	int now=rt;//從根開始找 
	while(x!=tr[now].c)
	{
		if(x<tr[now].c)//比目前點數值小 
		{
			if(tr[now].ch[0]==0)break;//沒有，隻好跳出循環 傳回目前這個now 是與x最貼切的節點 
			now=tr[now].ch[0];//走左邊 
		}
		else
		{
			if(tr[now].ch[1]==0)break;
			now=tr[now].ch[1];//走右邊 
		}
	}
	return now;
}

void add(int c,int x)//添加新節點 此處c是數值，x是新節點爸爸的編号  
{
	tot++;
	tr[tot].c=c;tr[tot].cnt=1;
	tr[tot].size=1;tr[tot].fa=x;
	tr[tot].ch[0]=tr[tot].ch[1]=0;
	if(c<tr[x].c)tr[x].ch[0]=tot;
	else tr[x].ch[1]=tot;//判斷新節點是爸爸的左兒子還是右兒子 
	return ;
}

void rotate(int x,int w)//單旋 此處x是編号 w是兒子标記 w等于1意味着我是我爸的左兒子，否則為我爸的右兒子
{
	int f=tr[x].fa,ff=tr[f].fa;
	tr[f].ch[1-w]=tr[x].ch[w];
	//這裡的ch[0]是左兒子，ch[1]是右兒子
	//如果我是我爸的右兒子，那麼說明我的整棵子樹都比他大，是以我的左兒子給我爸當右兒子
	//如果我是我爸的左兒子，那麼說明我的整棵子樹都比他小，是以我的右兒子給我爸當左兒子
	if(tr[x].ch[w]!=0)tr[tr[x].ch[w]].fa=f; 
	if(tr[ff].ch[0]==f)tr[ff].ch[0]=x;//爺爺>爸爸 
	else tr[ff].ch[1]=x;//爸爸是爺爺什麼兒子 我旋轉後就給爺爺當什麼兒子 
	tr[x].fa=ff;
	tr[f].fa=x;
	tr[x].ch[w]=f;
	update(f);//更新底層 
	update(x);//更新目前層 
}

void splay(int x,int goal)//把x旋到目标節點下面 
{
	while(tr[x].fa!=goal)
	{
		int f=tr[x].fa,ff=tr[f].fa;
		if(ff==goal)//爺爺就是目标
		{//旋一次就行 
			if(x==tr[f].ch[0])//我<我爸 
				rotate(x,1);
			else rotate(x,0);
		} 
		else
		{
			if(tr[ff].ch[0]==f)//爺爺>我爸 
			{
				if(tr[f].ch[0]==x)//我爸>我 
				{//我與我爸共線 則雙旋
					rotate(f,1);//我爸是我爺爺左兒子 
					rotate(x,1);//我是我爸左兒子 
					 
				}
				else
				{//我爸<我 
					rotate(x,0);//我是我爸右兒子 
					rotate(x,1);//現在我是我爺爺左兒子
				}
			} 
			else//爺爺<我爸 
			{ 
				if(tr[f].ch[0]==x)
				{
					rotate(x,1);//我是我爸左兒子 
					rotate(x,0);//現在我是我爺爺右兒子 
				}
				else
				{//我與我爸共線 則雙旋
					rotate(f,0);//我爸是我爺爺右兒子 
					rotate(x,0);//我是我爸右兒子 
				}
			}
		} 
	}
	if(goal==0)rt=x;
}

void insert(int x)//插入一個數 此處x是數值 
{
	if(rt==0)
	{//第一個節點 先讓你當0兒子 
		add(x,0);
		rt=tot;
		return ;
	}
	int ip=findip(x);//找出x數值的節點編号或是最貼近的節點 
	if(tr[ip].c==x)
	{//之前插入過這個數值 
		tr[ip].cnt++;
		update(ip);
		splay(ip,0);
	}
	else
	{
		add(x,ip);//新點 
		update(ip);
		splay(tot,0);
	}
}

void del(int x)//删除一個數 此處x是數值 
{
	int ip=findip(x);//拿它編号 
	splay(ip,0);//讓它當根 友善操作 
	if(tr[ip].c!=x)return ;//之前沒有插入過這個數值 
	if(tr[ip].cnt>1)
	{//不止一個這個數值 
		tr[ip].cnt--;
		update(ip);
	}
	else if(tr[ip].ch[0]==0&&tr[ip].ch[1]==0)//已經将這個點旋到根了 如果沒有左右兒子 說明整棵樹隻有一個點 
		rt=0,tot=0;
	else if(tr[ip].ch[0]!=0&&tr[ip].ch[1]==0)//隻有一個兒子就讓他繼承 
		rt=tr[ip].ch[0],tr[tr[ip].ch[0]].fa=0;
	else if(tr[ip].ch[1]!=0&&tr[ip].ch[0]==0)//隻有一個兒子就讓他繼承 
		rt=tr[ip].ch[1],tr[tr[ip].ch[1]].fa=0;
	else
	{
		int p=tr[ip].ch[0];
		while(tr[p].ch[1]!=0)p=tr[p].ch[1];//找前驅來 
		splay(p,ip);//旋到我這裡來，因為前驅是小于我中最大的 它此時沒有右兒子 
		rt=p;tr[p].fa=0;
		tr[tr[ip].ch[1]].fa=p;//直接把右兒子給它 
		tr[p].ch[1]=tr[ip].ch[1];
		update(p);
	}
}

int rank(int x)//此處x是數值 找出x的排名 
{
	int ip=findip(x);splay(ip,0);//把我旋成根 友善處理 
	return tr[tr[ip].ch[0]].size+1;//我是根 是以左子樹全小于我 +1就是我排名 
}

int kth(int x)//找排名是x的數值 
{
	int now=rt;
	while(1)
	{
		if(x<=tr[tr[now].ch[0]].size)//如果我小于左邊的個數 去左邊找 
			now=tr[now].ch[0];
		else if(tr[tr[now].ch[0]].size+tr[now].cnt<x)
		{//如果比左+目前自己還大 去右邊 
			x=x-tr[tr[now].ch[0]].size-tr[now].cnt;
			now=tr[now].ch[1];
		} 
		else break;//等于目前 
	}
	return tr[now].c;
}

int last(int x)//找前驅 此處x是數值 
{
	int ip=findip(x);
	splay(ip,0);
	if(x<=tr[ip].c&&tr[ip].ch[0]!=0)
	{
		ip=tr[ip].ch[0];
		while(tr[ip].ch[1]!=0)ip=tr[ip].ch[1];
	} //比我小最大的：左子樹最右的 
	if(x<=tr[ip].c)return 0;
	return tr[ip].c;
}

int next(int x)//找後繼 此處x是數值 
{
	int ip=findip(x);
	splay(ip,0);
	if(x>=tr[ip].c&&tr[ip].ch[1]!=0)
	{
		ip=tr[ip].ch[1];
		while(tr[ip].ch[0]!=0)ip=tr[ip].ch[0]; 
	} //比我大最小的:右子樹最左邊
	if(x>=tr[ip].c)return 0;
	return tr[ip].c;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int h,x;
		scanf("%d %d",&h,&x);
		if(h==1)
		insert(x);
		else if(h==2)
			del(x);
		else if(h==3)
			printf("%d\n",rank(x));
		else if(h==4)
			printf("%d\n",kth(x));
		else if(h==5)
			printf("%d\n",last(x));
		else if(h==6)
			printf("%d\n",next(x));
	}
} 
           

看了好多部落格 要昏了