求助
查看原帖
求助
341245
Sunflower_ac楼主2021/8/12 11:04

跟对拍了半天没对拍出来差异,提交上去全WA,实在不知道哪里错了(大概也可能是我的数据生成器写的有问题)

代码:

//luoguP5076
#include<iostream>
#include<cmath>
using namespace std;
const int maxn=1e4+10;
int val[maxn],siz[maxn],lc[maxn],rc[maxn],cnt[maxn];
int sum=0,minn,maxx,ans;

int queryrnk(int o,int v)
{
	if(!o) return 0;
	if(val[o]==v)return siz[lc[o]]+1;
	else if(val[o]>v) return queryrnk(lc[o],v);
    else if(val[o]<v)return queryrnk(rc[o],v)+siz[lc[o]]+cnt[o];
}

int querykth(int o,int k)
{
	while(o)
	{
		if(siz[lc[o]]>=k) o=lc[o];
		else if(siz[lc[o]]<k-cnt[o])
		{
			o=rc[o];
			k=k-siz[lc[o]]-cnt[o];
		}
		else return val[o];
	}
	return 2147483647;
}

int findmax(int o,int v)
{
	if(val[o]>=v)
	{
		if(lc[o])return findmax(lc[o],v);
		return maxx;
	}
	else
	{
		if(!rc[o])
		{
			if(val[o]<v)return val[o];//?
			return ans;
		}
		if(cnt[o]){maxx=val[o];return findmax(rc[o],v);}
		return findmax(rc[o],v);
	}
}

int findmin(int o,int v)
{
	if(val[o]<=v)
	{
		if(rc[o])return findmin(rc[o],v);
		return minn;
	}
	else 
	{
		if(!lc[o])
		{
			if(val[o]>v)return val[o];
			return ans;
		}
		if(cnt[o]){minn=val[o];return findmin(lc[o],v);}
		return findmin(lc[o],v);
	}
}

void insert(int &o,int v)
{
	if(!o)
	{
		val[o=++sum]=v;
		cnt[o]=siz[o]=1;
		lc[o]=rc[o]=0;
		return ;
	}
	siz[o]++;
	if(val[o]==v){cnt[o]++;return ;}
	if(val[o]>v) insert(lc[o],v);
	if(val[o]<v)insert(rc[o],v);
}

int main()
{
	//freopen("xrk.in.txt","r",stdin);
	//freopen("data.in","r",stdin);
	//freopen("xrk.out.txt","w",stdout); 
	int q;
	cin>>q;
	int opt,x,k=1;
	while(q--)
	{
		cin>>opt>>x;
		if(opt==1){ans=0;cout<<queryrnk(1,x)+1<<endl;}
		if(opt==2)cout<<querykth(1,x)<<endl;
		if(opt==3){maxx=-2147483647;cout<<findmax(1,x)<<endl;}
		if(opt==4){minn=2147483647;cout<<findmin(1,x)<<endl;}
		if(opt==5)insert(k,x);
	}
	return 0;
}

就想知道哪里错了(蒟蒻学BST三天了没A)

2021/8/12 11:04
加载中...