怀疑是前驱和后继那里出锅了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;
}