求助
查看原帖
求助
377434
tian_jun_cheng楼主2022/2/12 18:39
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+1;
int root,nn;
int lef[maxn],rig[maxn],val[maxn],num[maxn],siz[maxn];
void add(int r,int x)
{
	if(r==0)
	{
		r=++nn;
		val[nn]=x;
		num[nn]=1;
	}
	else if(val[r]==x)
		num[r]++;
	else if(x<val[r])
		add(lef[r],x);
	else
		add(rig[r],x);
	siz[r]=siz[lef[r]]+siz[rig[r]]+num[r];
}
int rnk(int r,int x)
{
	if(r==0)
		return 1;
	if(x<val[r])
		return rnk(lef[r],x);
	if(x==val[r])
		return siz[lef[r]]+1;
	return siz[lef[r]]+num[r]+rnk(rig[r],x);
}
int kth(int r,int k)
{
	if(k<=siz[lef[r]])
		return kth(lef[r],k);
	k-=siz[lef[r]];
	if(k<=num[r])
		return val[r];
	k-=num[r];
	return kth(rig[r],k);
}
int pre_e(int r,int x,int f)
{
	int d=kth(r,rnk(r,x)-1);
	return d>0 ? d : f;
}
int nex_e(int r,int x,int f)
{
	int d=kth(r,rnk(r,x+1));
	return d>0 ? d : f;
}
int main()
{
	int t;
	cin>>t;
	int cnt=0;
	while(t--)
	{
		int op,n;
		cin>>op>>n;
		if(op==1)
			cout<<rnk(1,n)+1<<endl;
		else if(op==2)
			cout<<kth(1,n)<<endl;
		else if(op==3)
			cout<<pre_e(1,n,-2147483647)<<endl;
		else if(op==4)
			cout<<nex_e(1,n,2147483647)<<endl;
		else
		{
			if(cnt==0)
			{
				cnt++;
				num[1]=siz[1]=1;
				val[1]=n;
			}
			else
				add(1,n);
		}
	}
	return 0;
}

请问kth函数哪里有问题啊

2022/2/12 18:39
加载中...