输出和题目完全一样但是WA...
已经调了一整天了 ;(
有没有大佬看一下 ;(
#include<bits/stdc++.h>
using namespace std;
struct A{
A* l;
A* r;
int val;//点的值(BST)
int fix;//修正值(堆)
int weight;//点出现次数
int sum;//子树个数(求排名 )
};
A* root;
int n,T,x;
int tag,nodesum;
void up(A* &root)
{
root->sum=root->weight;
if(root->l) root->sum+=root->l->sum;
if(root->r) root->sum+=root->r->sum;
}
A* zxuan(A* root)//左旋
{
if(root==NULL) return NULL;
A* q=root->r;
root->r=q->l;
q->l=root;
up(root);
up(q);
return q;
}
A* yxuan(A* root)//右旋
{
if(root==NULL) return NULL;
A* q=root->l;
root->l=q->r;
q->r=root;
up(root);
up(q);
return q;
}
A* cha(A* root,int val)//插入
{
if(root==NULL)
{
A* q=new A();
q->fix=rand()*rand();
q->val=val;
q->weight=1;
up(q);
return q;
}
if(val==root->val)//重复点
{
root->weight++;
return root;
}
if(val<root->val)//往左子树找
{
root->l=cha(root->l,val);
if(root->l->fix<root->fix)//小根堆
root=yxuan(root);
up(root);
return root;
}
else//往右子树找
{
root->r=cha(root->r,val);
if(root->r->fix<root->fix)//小根堆
root=zxuan(root);
up(root);
return root;
}
}
A* shan(A* root,int val)//删除
{
// ↓ 找
if(root==NULL) return NULL;
if(val<root->val)
{
up(root);
root->l=shan(root->l,val);
return root;
}
else if(val>root->val)
{
up(root);
root->r=shan(root->r,val);
return root;
}
// ↓ 找到了
if(root->weight>1)//有多个相同点
{
root->weight--;
up(root);
return root;
}//要删除当前点
if(root->l==NULL && root->r==NULL)//无儿子 =>直接删除
{
delete root;
return NULL;
}
if(root->l!=NULL && root->r!=NULL)//有两个儿子 =>
{
if(root->l->fix<root->r->fix)
{
root=yxuan(root);
up(root);
root->r=shan(root->r,val);
return root;
}
else
{
root=zxuan(root);
up(root);
root->l=shan(root->l,val);
return root;
}
}
if(root->l!=NULL)//只有左儿子 =>
{
A* q=root->l;
delete root;
return q;
}
else//只有右儿子 =>
{
A* q=root->r;
delete root;
return q;
}
}
int dian_lev(A* root,int val)//查点排名
{
if(root==NULL) return 0;
if(val==root->val)
{
if(root->l)
return root->l->sum;
else
return 0;
}
if(val>root->val)
{
if(root->l)
return root->l->sum+1+dian_lev(root->r,val);
else
return 1+dian_lev(root->r,val);
}
return dian_lev(root->l,val);
}
int lev_dian(A* root,int lev)//找排名点
{
if(root==NULL) return -1e7;
if(root->l)
{
if(lev==root->l->sum+1)//就是当前点
return root->val;
else if(lev>root->l->sum+1)//在右子树中
return lev_dian(root->r,lev-root->l->sum-1);
else//在左子树中
return lev_dian(root->l,lev);
}
else//没有左子树
{
if(lev==1)//就是当前点
return root->val;
else
return lev_dian(root->r,lev-1);
}
}
void zhaoqq(A* root,int val)//找前驱
{
if(root==NULL) return;
if(val>=root->val)
{
tag=root->val;
zhaoqq(root->r,val);
}
zhaoqq(root->l,val);
}
void zhaohj(A* root,int val)//找后继
{
if(root==NULL) return;
if(val<=root->val)
{
tag=root->val;
zhaohj(root->l,val);
}
zhaohj(root->r,val);
}
void sc(A* root)
{
cout<<"- ";
if(root!=NULL)
for(int i=1;i<=nodesum;i++)
cout<<lev_dian(root,i)<<" ";
cout<<" -\n";
}
void zhong(A* root)
{
if(root==NULL) return;
zhong(root->l);
cout<<root->val<<" ";
zhong(root->r);
}
int main()
{
freopen("5.in","r",stdin);
cin>>n;
while(n--)
{
tag=0;
scanf("%d%d",&T,&x);
if(T==1)
{
nodesum++;
root=cha(root,x);//插入
}
if(T==2)
{
nodesum--;
root=shan(root,x);//删除
}
if(T==3)
{
int num=dian_lev(root,x);//查点排名
printf("%d\n",num+1);
}
if(T==4)
{
int num=lev_dian(root,x);//找排名点
printf("%d\n",num);
}
if(T==5)
{
zhaoqq(root,x);//找前驱
printf("%d\n",tag);
}
if(T==6)
{
zhaohj(root,x);//找后继
printf("%d\n",tag);
}
}
}