求助Splay,样例都过不了
查看原帖
求助Splay,样例都过不了
224927
lei_yu楼主2020/8/18 19:19

一开始使用了奇怪的ls和rs,之后代码长度直接暴增。。

第一次打平衡树,调了一下午了,yyy...yyy...

如果码风奇怪请见谅,真心求助,谢谢各位神犇。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct node
{
	int ls,rs,fa,v,size,cnt;//左子树,右子树,父亲,节点存的值,子树大小,当前节点有多少个数。 
}a[1000005];
int n,q,p,root;
void splay_rotate(int x)
{
	int y=a[x].fa;
	int z=a[y].fa;
	if(a[z].ls==y)a[z].ls=x;
	else a[z].rs=x;
	a[x].fa=z;
	if(a[y].ls==x)
	{
		a[y].ls=a[x].rs;
		a[a[x].rs].fa=y;
		a[x].rs=y;
		a[y].fa=x;
	}
	else 
	{
		a[y].rs=a[x].ls;
		a[a[x].ls].fa=y;
		a[x].ls=y;
		a[y].fa=x;
	}
	a[x].size=a[a[x].ls].size+a[a[x].rs].size+a[x].cnt;
	a[y].size=a[a[y].ls].size+a[a[y].rs].size+a[y].cnt;
}
void splay(int x,int to)
{
	while(a[x].fa!=to)
	{
		int y=a[x].fa;
		int z=a[y].fa;
		if(z!=to)
		{
			if((a[z].ls==y)==(a[y].ls==x))
			{
				splay_rotate(y);
				splay_rotate(x);
			}
			else
			{	
				splay_rotate(x);
				splay_rotate(x);
			}
		}
		else splay_rotate(x);
	}
	if(!to)root=x;
}
int splay_find(int x)
{
	int u=root;
	while(a[u].v!=x)
	{
		if(a[u].v<u)
		{
			if(!a[u].rs)break;
			u=a[u].rs;
		}
		else
		{
			if(!a[u].ls)break;
			u=a[u].ls;
		}
	}
	splay(u,0);
	return a[a[u].ls].size;
}
int splay_rfind(int x)
{
	int u=root;
	while(1)
	{
		if(x<=a[u].cnt+a[a[u].ls].size)
		{
			if(x>a[a[u].ls].size)return a[u].v;
			u=a[u].ls;
		}
		else
		{
			x-=(a[u].cnt+a[a[u].ls].size);
			u=a[u].rs;
		}
	}
}
void splay_insert(int x)
{
	int u=root;
	int father=0;
	while(u&&a[u].v!=x)
	{
		father=u;
		if(a[u].v>x)u=a[u].ls;
		else u=a[u].rs;
	}
	if(u)a[u].cnt++;
	else
	{
		u=++n;
		if(father)
		{
			if(a[father].v>x)a[father].ls=u;
			else a[father].rs=u;
		}
		a[u].cnt=1;
		a[u].size=1;
		a[u].v=x;
		a[u].fa=father;
		a[u].ls=0;
		a[u].rs=0;
	}
	splay(u,0);
}
int splay_big(int x)
{
	splay_find(x);
	int u=root;
	if(x<a[root].v)return a[root].v;
	u=a[root].rs;
	while(a[u].ls)u=a[u].ls;
	return a[u].v;
}
int splay_small(int x)
{
	splay_find(x);
	int u=root;
	if(x>a[root].v)return a[root].v;
	u=a[root].ls;
	while(a[u].rs)u=a[u].rs;
	return a[u].v;
}
void splay_delete(int x)
{
	int last=splay_small(x);
	int next=splay_big(x);
	splay(last,0);
	splay(next,last);
	int del=a[next].ls;
	if(a[del].cnt>1)
	{
		a[del].cnt--;
		splay(del,0);
	}
	else a[next].ls=0;
}
int main()
{
	splay_insert(0x7fffffff);
	splay_insert(-0x7fffffff);
	int x,y;
	cin>>p;
	for(int i=1;i<=p;i++)
	{
		scanf("%d%d",&x,&y);
		if(x==1)splay_insert(y);
		else if(x==2)splay_delete(y);
		else if(x==3)printf("%d\n",splay_find(y));
		else if(x==4)printf("%d\n",splay_rfind(y));
		else if(x==5)printf("%d\n",splay_small(y));
		else if(x==6)printf("%d\n",splay_big(y));
	}
}

HELP ME!!!!!

2020/8/18 19:19
加载中...