原题链接:https://www.luogu.com.cn/problem/P3369
题意:
您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:
- 插入 xx 数
- 删除 xx 数(若有多个相同的数,因只删除一个)
- 查询 xx 数的排名(排名定义为比当前数小的数的个数 +1 )
- 查询排名为 xx 的数
- 求 xx 的前驱(前驱定义为小于 xx,且最大的数)
- 求 xx 的后继(后继定义为大于 xx,且最小的数)
思路:
可以看讲解视频:https://www.bilibili.com/video/BV15b411H7Wg?t=185&p=2
代码:
#include <bits/stdc++.h> using namespace std; #define ls(x) arr[x].child[0] #define rs(x) arr[x].child[1] const int N = 1e7+10; struct node{ int child[2],size,value,key; }arr[N]; int tot; inline void Push_Up(int index){ arr[index].size=arr[ls(index)].size+arr[rs(index)].size+1; } inline void split(int root,int& x,int& y,int value){//理解时,我们可以把x当做是答案的第一个,y当做答案的第二个,这个函数的意义是:将以root为根的树按照value分为以x为根的树和以y为根的树。注意引用的作用 if(!root){ x=y=0;//分到底了,返回 return; } if(arr[root].value<=value){//如果比它小 x=root;//那么value肯定在root的右子树里,先将root贴到第一个答案上 split(rs(root),rs(x),y,value);//把第一个答案的右子树按value分开,得到答案(这里自己理解一下,不难懂) }else{//反之亦然 y=root; split(ls(root),x,ls(y),value); } Push_Up(root); } inline void split1(int root,int& x,int& y,int value){ if(!root){ x=y=0; return; } if(arr[ls(root)].size+1<=value){ x=root; split(rs(x),rs(x),y,value-arr[ls(root)].size-1);//注意这里有些变化 }else{ y=root; split(ls(y),x,ls(y),value); } Push_Up(root); } inline void merge(int& root,int x,int y){//函数名的意义是:把以x为根的树和以y为根的树合并为以root为根的树 if(!x||!y){//合并到底,返回 root=x+y; return; } if(arr[x].key<arr[y].key){//默认大根堆 root=x;//先把x挂到root上 merge(rs(root),rs(x),y);//注意要满足BST性质 }else{//反之亦然 root=y; merge(ls(root),x,ls(y)); } Push_Up(root); } inline void insert(int& root, int value){ int x=0,y=0,z=++tot; arr[z].value=value,arr[z].size=1,arr[z].key=rand(); split(root,x,y,value); merge(x,x,z); merge(root,x,y); } inline void erase(int& root, int value){ int x=0,y=0,z=0; split(root,x,y,value); split(x,x,z,value-1); merge(z,ls(z),rs(z)); merge(x,x,z); merge(root,x,y); } inline int kth_number(int root, int k){ while(arr[ls(root)].size+1!=k){ if(arr[ls(root)].size>=k){ root=ls(root); }else{ k-=(arr[ls(root)].size+1); root=rs(root); } } return arr[root].value; } inline int get_rank(int& root,int value){ int x=0,y=0; split(root,x,y,value-1); int res=arr[x].size+1; merge(root,x,y); return res; } inline int pre(int& root, int value){ int x=0,y=0; split(root,x,y,value-1); int res=kth_number(x,arr[x].size); merge(root,x,y); return res; } inline int suf(int& root, int value){ int x=0,y=0; split(root,x,y,value); int res=kth_number(y,1); merge(root,x,y); return res; } int t,op,root; int main(){ srand(time(0)); cin>>t; while(t--){ int x; cin>>op>>x; if(op==1){ insert(root,x); }else if(op==2){ erase(root,x); }else if(op==3){ cout<<get_rank(root,x)<<endl; }else if(op==4){ cout<<kth_number(root,x)<<endl; }else if(op==5){ cout<<pre(root,x)<<endl; }else{ cout<<suf(root,x)<<endl; } } return 0; }