题目：您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
平衡树的模板题，借这个题整理一下平衡树；
核心是维护一颗二叉树的中序遍历，以中序遍历的先后表示维护的序列。
对于上图，两棵树的中序遍历均c2.B.c3.A.c1，故可以用这种方式交换B,A的位置。
对于插入x，只需要找到与x最接近的点P，然后根据大小插入左或右儿子。
5，6 操作只需将x旋到根节点，其左子树的最右边的节点和右子树的最左边的节点就是前驱与后驱。这里要注意x不一定在树中，在操作之前需要先插入x，在最后删去。树中也可能有多个x点，查询时需要找到第一位或最后一位。
3，4 操作维护每个节点下共有多少个节点就可快速得出来，每次旋转，两个节点的子树没有改变，所以只需要维护交换的两节点A,B。
删除x，将x点的前一个点旋到根，再将x的后一个点旋到根节点的右儿子处，在中序遍历中，左边的点都比该点靠前，右边的点比该点靠后。所以之后x就被旋到后一个点的左儿子的位置。只要将左儿子的指针归零就可以了。在删除时，如果x为第一个或最后一个就会没有前驱或后驱，所以开始是要先向树中加入一个极大值和一个极小值。
/**************************************************************
Problem: 3224
User: 1115825064
Language: C++
Result: 正确
Time:644 ms
Memory:3228 kb
****************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct D{
int w,lc,rc,size,fa;
}a[100005];
int tot=0,root=0;
void update(int x)
{
a[x].size=a[a[x].lc].size+a[a[x].rc].size+1;
}
void xuan1(int x)
{
int y=a[x].fa;
int z=a[y].fa;
a[a[x].lc].fa=y;
a[y].rc=a[x].lc;
a[x].lc=y;
a[x].fa=z;
a[y].fa=x;
if(a[z].lc==y) a[z].lc=x;
else a[z].rc=x;
update(y);
update(x);
}
void xuan2(int x)
{
int y=a[x].fa;
int z=a[y].fa;
a[a[x].rc].fa=y;
a[y].lc=a[x].rc;
a[x].rc=y;
a[x].fa=z;
a[y].fa=x;
if(a[z].lc==y) a[z].lc=x;
else a[z].rc=x;
update(y);
update(x);
}
void splay(int x,int wz)
{
while(a[x].fa!=wz)
{
int y=a[x].fa;
if(a[y].lc==x) xuan2(x);
else xuan1(x);
}
if(wz==0) root=x;
}
void new_node(int fa,int w,int &x)
{
x=++tot;
a[tot].fa=fa;
a[tot].w=w;
}
int search(int x)
{
int i,j=root;
while(j)
{
i=j;
if(a[j].w>x) j=a[j].lc;
else j=a[j].rc;
}
return i;
}
void jia(int x)
{
if(root==0)
{
new_node(0,x,root);
return ;
}
int y=search(x);
if(x<a[y].w) new_node(y,x,a[y].lc);
else new_node(y,x,a[y].rc);
splay(tot,0);
update(root);
}
int get(int x)
{
int ans=tot+1;
int i=root;
while(i)
{
if(a[i].w==x)
ans=i;
if(a[i].w>=x) i=a[i].lc;
else i=a[i].rc;
}
if(ans==tot+1) return -1;
else return ans;
}
int max(int x)
{
while(a[x].rc) x=a[x].rc;
return x;
}
int min(int x)
{
while(a[x].lc) x=a[x].lc;
return x;
}
void shan(int x)
{
int y=get(x);
if(y==-1) return ;
splay(y,0);
int ll=max(a[y].lc),rr=min(a[y].rc);
splay(ll,0);
splay(rr,root);
a[rr].lc=0;
update(rr);
update(ll);
}
int find(int x)
{
int y=get(x);
splay(y,0);
return a[a[y].lc].size;
}
int findth(int x,int wz)
{
if(x==a[a[wz].lc].size+1) return a[wz].w;
if(x<=a[a[wz].lc].size) return findth(x,a[wz].lc);
else return findth(x-a[a[wz].lc].size-1,a[wz].rc);
}
int qian(int x)
{
jia(x);
int y=get(x);
splay(y,0);
int ans=max(a[y].lc);
shan(x);
return a[ans].w;
}
int hou(int x)
{
jia(x);
int ans=min(a[tot].rc);
shan(x);
return a[ans].w;
}
void B(int x)
{
if(a[x].lc!=0) B(a[x].lc);
printf("%d ",a[x].w);
if(a[x].rc!=0) B(a[x].rc);
return ;
}
int main()
{
// freopen("1.txt","r",stdin);
int T;
scanf("%d",&T);
jia(-10000010);
jia(10000010);//预处理加入极大值和极小值。
while(T--)
{
int k,x;
scanf("%d%d",&k,&x);
if(k==1) jia(x);
if(k==2) shan(x);
if(k==3) printf("%d\n",find(x));
if(k==4) printf("%d\n",findth(x+1,root));//注意树中多了两个元素。
if(k==5) printf("%d\n",qian(x));
if(k==6) printf("%d\n",hou(x)); //B(root);printf("\n");
}
return 0;
}
评论 (0)
