题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
-
插入x数
-
删除x数(若有多个相同的数，因只删除一个)
-
查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
-
查询排名为x的数
-
求x的前驱(前驱定义为小于x，且最大的数)
- 求x的后继(后继定义为大于x，且最小的数)
输入输出格式
输入格式：第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号( 1≤opt≤6 1 \leq opt \leq 6 1≤opt≤6 )
输出格式：对于操作3,4,5,6每行输出一个数，表示对应答案
输入输出样例
输入样例#1：10 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598输出样例#1：
106465 84185 492737
说明
时空限制：1000ms,128M
1.n的数据范围： n≤100000
2.每个数的数据范围： [−107,107]
来源：Tyvj1728 原名：普通平衡树
在此鸣谢
Solution：
本题需要的6种操作的splay实现原理见此
splay代码：
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
#define son(x) (ch[fa[x]][1]==x)
using namespace std;
const int N=100005,inf=0x7fffffff;
int ch[N][2],fa[N],siz[N],rk[N],date[N],root,cnt,n,tot;
int gi(){
int a=0;char x=getchar();bool f=0;
while((x<'0'||x>'9')&&x!='-') x=getchar();
if(x=='-') x=getchar(),f=1;
while(x>='0'&&x<='9') a=(a<<3)+(a<<1)+(x^48),x=getchar();
return f?-a:a;
}
il void pushup(int rt){
int ls=ch[rt][0],rs=ch[rt][1];
siz[rt]=siz[ls]+siz[rs]+rk[rt];
}
il void rotate(int x){
int y=fa[x],z=fa[y],b=son(x),c=son(y),a=ch[x][!b];
z?ch[z][c]=x:root=x; fa[x]=z;
if(a)fa[a]=y; ch[y][b]=a;
ch[x][!b]=y,fa[y]=x;
pushup(y),pushup(x);
}
il void splay(int x,int i){
while(fa[x]!=i){
RE int y=fa[x],z=fa[y];
if(z==i) rotate(x);
else {
if(son(x)==son(y)) rotate(y),rotate(x);
else rotate(x),rotate(x);
}
}
}
void insert(int &rt,int x){
if(!rt){
rt=++cnt,date[cnt]=x,siz[cnt]=rk[cnt]=1;
return;
}
if(x==date[rt]){rk[rt]++,siz[rt]++;return;}
if(x<date[rt])
insert(ch[rt][0],x),fa[ch[rt][0]]=rt;
else
insert(ch[rt][1],x),fa[ch[rt][1]]=rt;
pushup(rt);
}
il int getpre(int rt,int x){
int p=rt,ans;
while(p){
if(x<=date[p]) p=ch[p][0];
else ans=p,p=ch[p][1];
}
return ans;
}
il int getsuc(int rt,int x){
int p=rt,ans;
while(p){
if(x>=date[p]) p=ch[p][1];
else ans=p,p=ch[p][0];
}
return ans;
}
il int getmin(int rt){
int p=rt,ans=-1;
while(p) ans=p,p=ch[p][0];
return ans;
}
void del(int rt,int x){
if(date[rt]==x) {
if(rk[rt]>1) rk[rt]--,siz[rt]--;
else {
splay(rt,0);
int p=getmin(ch[rt][1]);
if(~p) {
splay(p,rt);
root=p,fa[p]=0;
ch[p][0]=ch[rt][0],fa[ch[rt][0]]=p;
pushup(p);
}
else {
root=ch[rt][0],fa[ch[rt][0]]=0;
}
}
return ;
}
if(x<date[rt]) del(ch[rt][0],x);
else del(ch[rt][1],x);
pushup(rt);
}
int getrank(int rt,int x){
if(x==date[rt]){
splay(rt,0);
if(!ch[rt][0]) return 1;
return siz[ch[rt][0]]+1;
}
if(x<date[rt]) return getrank(ch[rt][0],x);
return getrank(ch[rt][1],x);
}
int getorder(int rt,int k){
int ls=ch[rt][0];
if(siz[ls]+1<=k&&k<=siz[ls]+rk[rt]) return date[rt];
if(k<siz[ls]+1) return getorder(ch[rt][0],k);
if(siz[ls]+rk[rt]<k) return getorder(ch[rt][1],k-siz[ls]-rk[rt]);
}
int main(){
n=gi();
while(n--){
RE int opt=gi(),x=gi();
if(opt==1) tot++,insert(root,x),splay(cnt,0),root=cnt;
if(opt==2) tot--,del(root,x);
if(opt==3) printf("%d\n",getrank(root,x));
if(opt==4) printf("%d\n",getorder(root,x));
if(opt==5) printf("%d\n",date[getpre(root,x)]);
if(opt==6) printf("%d\n",date[getsuc(root,x)]);
}
return 0;
}
本题用Treap的实现：引用自hzwer的博客
这是一道平衡树的模板题
treap是一棵修改了结点顺序的二叉查找树
通常树内的每个结点x都有一个关键字值key[x]，另外，还要为结点分配一个随机数。
假设所有的优先级是不同的，所有的关键字也是不同的。treap的结点排列成让关键字遵循二叉查找树性质，并且优先级遵
循最小堆顺序性质：
1.如果v是u的左孩子，则key[v] < key[u].
2.如果v是u的右孩子，则key[v] > key[u].
3.如果v是u的孩子，则rand[u] > rand[u].
这两个性质的结合就是为什么这种树被称为“treap”的原因，因为它同时具有二叉查找树和heap的特征。
Treap代码：
#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;
const int N=1e6+10;
struct tree{
int l,r;//左右儿子节点编号
int num;//当前节点的数字
int s;//以当前节点为根的子树的节点数
int sum;//当前节点的数字的数量
int rnd;//随机优先级
}tr[N];//下标为节点编号
int n,rt,cnt,t1,t2;
void updata(int &k){
int &l=tr[k].l,&r=tr[k].r;
tr[k].s=tr[l].s+tr[r].s+tr[k].sum;
}
void lturn(int &k){
int t=tr[k].r;tr[k].r=tr[t].l;tr[t].l=k;
tr[t].s=tr[k].s;updata(k);k=t;
}
void rturn(int &k){
int t=tr[k].l;tr[k].l=tr[t].r;tr[t].r=k;
tr[t].s=tr[k].s;updata(k);k=t;
}
void insert(int &k,int x){
if(!k){
k=++cnt;tr[k].num=x;tr[k].s=1;tr[k].sum++;tr[k].rnd=rand();return ;
}
tr[k].s++;
int &l=tr[k].l,&r=tr[k].r;
if(x<tr[k].num){
insert(l,x);
if(tr[l].rnd<tr[k].rnd) rturn(k);
}
else if(x>tr[k].num){
insert(r,x);
if(tr[r].rnd<tr[k].rnd) lturn(k);
}
else{
tr[k].sum++;return ;
}
}
void del(int &k,int x){
if(!k) return ;
int &l=tr[k].l,&r=tr[k].r;
if(x==tr[k].num){
if(tr[k].sum>1){
tr[k].sum--;tr[k].s--;return ;
}
if(l*r==0) k=l+r;
else{
if(tr[l].rnd<tr[r].rnd) rturn(k);
else lturn(k);
del(k,x);
}
}
else{
tr[k].s--;
if(x>tr[k].num) del(r,x);
else del(l,x);
}
}
int find1(int &k,int x){
if(!k) return 0;
int &l=tr[k].l,&r=tr[k].r;
if(tr[k].num==x) return tr[l].s+1;
if(tr[k].num>x) return find1(l,x);
if(tr[k].num<x) return tr[l].s+tr[k].sum+find1(r,x);
}
int find2(int &k,int x){
if(!k) return 0;
int &l=tr[k].l,&r=tr[k].r;
if(tr[l].s+1<=x&&tr[l].s+tr[k].sum>=x) return tr[k].num;
if(tr[l].s>=x) return find2(l,x);
if(tr[l].s+tr[k].sum<x) return find2(r,x-tr[l].s-tr[k].sum);
}
void pred(int &k,int x){
if(!k) return ;
int &l=tr[k].l,&r=tr[k].r;
if(tr[k].num<x){
t1=tr[k].num;
pred(r,x);
}
else pred(l,x);
}
void succ(int &k,int x){
if(!k) return ;
int &l=tr[k].l,&r=tr[k].r;
if(tr[k].num>x){
t2=tr[k].num;
succ(l,x);
}
else succ(r,x);
}
int main(){
srand(time(0));
scanf("%d",&n);
for(int i=1,opt,x;i<=n;i++){
scanf("%d%d",&opt,&x);t1=t2=0;
switch(opt){
case 1:insert(rt,x);break;
case 2:del(rt,x);break;
case 3:printf("%d\n",find1(rt,x));break;
case 4:printf("%d\n",find2(rt,x));break;
case 5:pred(rt,x);printf("%d\n",t1);break;
case 6:succ(rt,x);printf("%d\n",t2);break;
}
}
return 0;
}
无旋Treap的实现原理可以去看神犇fhq在wc上的ppt。
我大概讲下：用到了函数式编程的思想，所谓函数就是定义域+对应法则，所谓编程就是把输入映射成输出的函数。函数式编程从不修改任何东西，它只做一件事：定义。那么我们可以引申出函数式线段树（可持久化线段树），同理可以引申出函数式平衡树。但是平衡树需要旋转，很不方便，以treap为例，我们完全没必要旋转。只需用到两个操作：
1、merge：我们假设要把A、B两棵树合并（注意：中序遍历A<B，要保证合并后的树中序遍历满足该条件），若A、B一方为空返回另一方，若A的优先级大于B的优先级，则A作根递归合并A的右子树和B，否则B作根递归合并A和B的左子树。
2、split：我们假设把root为根的树按照小于等于权值k分为A、B两棵树，若当前节点val<=k则把其和左子树分给A并递归右子树，否则把其和右子树分给B并递归左子树。
有了这两个操作，其它操作都可以引申出来了（某些操作当然也可以像普通treap那样查）：
1、insert(x)，先split(x)，再把新节点与分离的两棵树二次merge。
2、delet(x)，先split(x)再split(x-1)，然后merge权值全为x的那棵树的左右子树。
3、rank(x)，先split(x-1)，排名就是权值小于等于x-1的那棵树的大小+1。
4、kth(x)，普通treap那样查。
5、pre(x)，先split(x-1)，再在权值小于等于x-1的那棵树中查kth(siz)。
6、suc(x)，先split(x)，再在权值大于x的那棵树中查kth(1)。
无旋Treap代码：
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=100005;
int n,cnt,root;
int ch[N][2],date[N],rnd[N],siz[N];
int gi(){
int a=0;char x=getchar();bool f=0;
while((x<'0'||x>'9')&&x!='-') x=getchar();
if(x=='-') x=getchar(),f=1;
while(x>='0'&&x<='9') a=(a<<3)+(a<<1)+(x^48),x=getchar();
return f?-a:a;
}
il int newnode(int v){
cnt++;
siz[cnt]=1,date[cnt]=v,rnd[cnt]=rand();
return cnt;
}
il void pushup(int rt){siz[rt]=siz[ch[rt][0]]+siz[ch[rt][1]]+1;}
int merge(int x,int y){
if(!x||!y) return x+y;
if(rnd[x]<rnd[y]) {
ch[x][1]=merge(ch[x][1],y);
pushup(x);
return x;
}
else {
ch[y][0]=merge(x,ch[y][0]);
pushup(y);
return y;
}
}
void split(int rt,int k,int &x,int &y){
if(!rt) {x=y=0;return;}
if(date[rt]<=k) x=rt,split(ch[rt][1],k,ch[rt][1],y);
else y=rt,split(ch[rt][0],k,x,ch[rt][0]);
pushup(rt);
}
il int kth(int rt,int k){
while(1){
if(k<=siz[ch[rt][0]]) rt=ch[rt][0];
else if(k>siz[ch[rt][0]]+1) k-=siz[ch[rt][0]]+1,rt=ch[rt][1];
else return rt;
}
}
il void ins(int v){
int x=0,y=0; split(root,v,x,y);
root=merge(x,merge(newnode(v),y));
}
il void del(int v){
int x=0,y=0,z=0;
split(root,v,x,z),split(x,v-1,x,y);
y=merge(ch[y][0],ch[y][1]);
root=merge(x,merge(y,z));
}
il int id(int v){
int x=0,y=0,ans; split(root,v-1,x,y);
ans=siz[x]+1; root=merge(x,y);
return ans;
}
il int pre(int v){
int x=0,y=0,ans; split(root,v-1,x,y);
ans=date[kth(x,siz[x])]; root=merge(x,y);
return ans;
}
il int suc(int v){
int x=0,y=0,ans; split(root,v,x,y);
ans=date[kth(y,1)]; root=merge(x,y);
return ans;
}
int main(){
srand(time(0));
n=gi();
int opt,v;
while(n--){
opt=gi(),v=gi();
if(opt==1) ins(v);
if(opt==2) del(v);
if(opt==3) printf("%d\n",id(v));
if(opt==4) printf("%d\n",date[kth(root,v)]);
if(opt==5) printf("%d\n",pre(v));
if(opt==6) printf("%d\n",suc(v));
}
return 0;
}
用vector暴力模拟可以AC，总耗时也就比正解慢100ms左右
vector代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<vector>
#include<algorithm>
#define inf 1000000000
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n;
vector<int> a;
void insert(int x)
{
a.insert(upper_bound(a.begin(),a.end(),x),x);
return;
}
void del(int x)
{
a.erase(lower_bound(a.begin(),a.end(),x));
return;
}
int find(int x)
{
return lower_bound(a.begin(),a.end(),x)-a.begin()+1;
}
int main()
{
n=read();
a.reserve(200000);
int f,x;
for(int i=1;i<=n;i++)
{
f=read();x=read();
switch(f)
{
case 1:insert(x);break;
case 2:del(x);break;
case 3:printf("%d\n",find(x));break;
case 4:printf("%d\n",a[x-1]);break;
case 5:printf("%d\n",*--lower_bound(a.begin(),a.end(),x));break;
case 6:printf("%d\n",*upper_bound(a.begin(),a.end(),x));break;
}
}
return 0;
}
用pbds中的红黑树的AC实现代码（竟然比vector的暴力模拟还慢上100ms，贼有意思！）：
#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
#define il inline
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>t;
il int gi()
{
int a=0;char x=getchar();bool f=0;
while((x<'0'||x>'9')&&x!='-')x=getchar();
if(x=='-')x=getchar(),f=1;
while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
return f?-a:a;
}
ll n,opt,x,ans;
int main()
{
t T;
n=gi();
for(int i=1;i<=n;i++){
opt=gi(),x=gi();
if(opt==1)T.insert((x<<20)+i);
if(opt==2)T.erase(T.lower_bound(x<<20));
if(opt==3)printf("%lld\n",T.order_of_key(x<<20)+1);
if(opt==4){ans=*T.find_by_order(x-1),printf("%lld\n",ans>>20);}
if(opt==5){ans=*--T.lower_bound(x<<20),printf("%lld\n",ans>>20);}
if(opt==6){ans=*T.upper_bound((x<<20)+n),printf("%lld\n",ans>>20);}
}
return 0;
}