BST 样例全对零分求调
查看原帖
BST 样例全对零分求调
277757
hanyuchen2019楼主2021/9/11 16:47

怀疑是前驱和后继那里出锅了qwq

有没有dalao帮忙调一下,感激不尽

#include<iostream>
using namespace std;
#define reg register int
#define INF 2147483647
struct node
{
	int a,ls,rs,cnt,siz;//值,左儿子下标,右儿子下标,出现次数,大小
}tree[500005];
int cont;
void _new(int val)
{
	cont++;
	tree[cont].cnt=tree[cont].siz=1;
	tree[cont].a=val;
}
void charu(int x,int v)
{
	tree[x].siz++;
	if(tree[x].a==v)
	{
		tree[x].cnt++;
		return;
	}
	if(tree[x].a>v)
	{
		if(tree[x].ls)
			charu(tree[x].ls,v);
		else
		{
			_new(v);
			tree[x].ls=cont;
		}
	}
	else
	{
		if(tree[x].rs)
			charu(tree[x].rs,v);
		else
		{
			_new(v);
			tree[x].rs=cont;
		}
	}
}
int qianqu(int x,int v,int ans)
{
	if(tree[x].a>=v)
	{
		if(!tree[x].ls)
			return ans;
		return qianqu(tree[x].ls,v,ans);
	}
	else
	{
		if(!tree[x].rs)
			return tree[x].a<v?tree[x].a:ans;
		if(tree[x].cnt)
			return qianqu(tree[x].rs,v,tree[x].a);
		return qianqu(tree[x].rs,v,ans);
	}
}
int houji(int x,int v,int ans)
{
	if(tree[x].a<=v)
	{
		if(!tree[x].rs)
			return ans;
		return houji(tree[x].rs,v,ans);
	}
	else
	{
		if(!tree[x].ls)
			return tree[x].a>v?tree[x].a:ans;
		if(tree[x].cnt)
			return houji(tree[x].ls,v,tree[x].a);
		return houji(tree[x].ls,v,ans);
	}
}
int findrk(int x,int v)
{
	if(!x)return 0;
	if(tree[x].a==v)
		return tree[tree[x].ls].siz;
	if(tree[x].a>v)
		return findrk(tree[x].ls,v);
	else
		return findrk(tree[x].rs,v)+tree[tree[x].ls].a+tree[x].cnt;
}
int findval(int x,int rk)
{
	if(!x)return INF;
	if(tree[tree[x].ls].siz>=rk)
		return findval(tree[x].ls,rk);
	if(tree[tree[x].ls].siz+tree[x].cnt>=rk)
		return tree[x].a;
	return findval(tree[x].rs,rk-tree[x].cnt-tree[tree[x].ls].siz);
}
int main()
{
	ios::sync_with_stdio(false);
	int q;
	cin>>q;
	while(q--)
	{
		int a,b;
		cin>>a>>b;
		if(a==1)
			cout<<findrk(1,b)+1<<endl;
		if(a==2)
			cout<<findval(1,b)<<endl;
		if(a==3)
			cout<<qianqu(1,b,-INF)<<endl;
		if(a==4)
			cout<<houji(1,b,INF)<<endl;
		if(a==5)
		{
			if(!cont)
				_new(b);
			else
				charu(1,b);
			//for(int i=1;i<=cont;i++)cout<<"-t-"<<i<<":"<<tree[i].a<<" "<<tree[i].cnt<<" "<<tree[i].ls<<" "<<tree[i].rs<<" "<<tree[i].siz<<endl;
		}
	}
 	return 0;
}

2021/9/11 16:47
加载中...