不知道哪错了 求调
#include<bits/stdc++.h>
using namespace std;
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
int n,opt,x,inf=1<<30;
struct node
{
int key,rank,size,cnt;
node *son[2];
bool operator <(const node a)const{return rank<a.rank;}
int cmp(int x)const
{
if(key==x)return -1;
return x<key?0:1;
}
void update()
{
size=cnt;
if(son[0]!=NULL)size+=son[0]->size;
if(son[1]!=NULL)size+=son[1]->size;
}
};
void rotate(node *&o,int d)//转
{
node *k=o->son[d^1];
o->son[d^1]=k->son[d];
k->son[d]=o;
o->update();
k->update();
o=k;
}
void insert(node *&o,int k)//插入节点
{
if(o==NULL)
{
o=new node();
o->son[0]=o->son[1]=NULL;
o->rank=rand();
o->key=k;
o->size=1;
o->cnt=1;
}
else if(o->key==k)
{
o->cnt++;
}
else
{
int d=o->cmp(k);
insert(o->son[d],k);
if(o<o->son[d])rotate(o,d^1);
}
o->update();
}
void remove(node *&o,int k)//删节点
{
int d=o->cmp(k);
if(d==-1)
{
if(o->cnt>1)
{
o->cnt--;
o->update();
return ;
}
else
{
node *x=o;
if(o->son[0]!=NULL&&o->son[1]!=NULL){
int d1=o->son[1]->rank<o->son[0]->rank?1:0;
rotate(o,d1);
remove(o->son[d1],k);
}
else{
if(o->son[0]==NULL)o=o->son[1];
else o=o->son[0];
delete x;
}
}
}else remove(o->son[d],k);
if(o!=NULL)o->update();
}
int kth(node *o,int k)//找第k个
{
if(o==NULL||k<=0||k>o->size)return -1;
int x=o->son[0]==NULL?0:o->son[0]->size;
if(x+1<=k&&x+o->cnt>=k)return o->key;
if(k<=x)return kth(o->son[0],k);
else return kth(o->son[1],k-o->cnt-x);
}
int find(node *o,int k)找k是第几个
{
if(o==NULL)return -1;
int d=o->cmp(k);
if(d==-1){
return o->son[0]==NULL?1:1+o->son[0]->size;
}
if(d==0)return find(o->son[0],k);
else {
int t=find(o->son[1],k);
if(t==-1)return -1;
return o->son[0]==NULL?t+o->cnt:t+o->cnt+o->son[0]->size;
}
}
int fpre(node *o,int k)//前驱
{
int pre=-inf;
while(o!=NULL)
{
if(o->key>=k)o=o->son[0];
else{
pre=o->key;
o=o->son[1];
}
}
return pre;
}
int fnxt(node *o,int k)//后驱
{
int nxt=inf;
while(o!=NULL)
{
if(o->key<=k)o=o->son[1];
else{
nxt=o->key;
o=o->son[0];
}
}
return nxt;
}
int main()
{
n=read();
node *root=new node();
for(int i=1;i<=n;i++)
{
opt=read();
x=read();
if(opt==1)insert(root,x);
if(opt==2)remove(root,x);
if(opt==3){
printf("%d\n",find(root,x));
}
if(opt==4){
printf("%d\n",kth(root,x));
}
if(opt==5)printf("%d\n",fpre(root,x));
if(opt==6)printf("%d\n",fnxt(root,x));
}
return 0;
}
好像是很多输出1的地方我输出0了,但不知道为什么