跟对拍了半天没对拍出来差异,提交上去全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)