平衡树treap(带旋treap)
带旋treap 注意左右旋转可以合并，d=1时 左儿子上旋至根节点，d==0时右儿子上旋至根节点 代码见下：
void zhuan(int &x,int d){//旋转，d=1是左儿子上旋
int son=t[x].ch[d];
t[x].ch[d]=t[son].ch[d^1];
t[son].ch[d^1]=x;
up(x),up(x=son);
}
有zz问我ac没有，废话，我都发博客了还能没ac吗？（滑稽）
全部代码见下
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,inf=0x3f3f3f3f;
inline int get(){
int res=0,flag=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')flag=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
res=res*10+c-'0';
c=getchar();
}
return res*flag;
}
struct node{
int ch[2],cnt,size,val,rd;//依次为左右儿子，有几个这么大的数，根和子节点总个数，值，随机排名
}t[N];
int tot=0;
struct treap{
#define ls t[x].ch[0]
#define rs t[x].ch[1]
void up(int x){//向上更新size
t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].cnt;
}
void zhuan(int &x,int d){//旋转，d=1是左儿子上旋
int son=t[x].ch[d];
t[x].ch[d]=t[son].ch[d^1];
t[son].ch[d^1]=x;
up(x),up(x=son);
}
void insert(int &x,int val){//插入
if(!x){
x=++tot;
t[x].cnt=t[x].size=1;
t[x].val=val;t[x].rd=rand();
return ;
}
t[x].size++;
if(t[x].val==val){
t[x].cnt++;return;
}
int d=t[x].val<val;insert(t[x].ch[d],val);
if(t[x].rd>t[t[x].ch[d]].rd)zhuan(x,d);
}
void shan(int &x,int val){//删数
if(!x)return ;
if(t[x].val==val){
if(t[x].cnt>1){
t[x].cnt--;t[x].size--;
return ;
}
bool d=t[ls].rd>t[rs].rd;
if(!ls||!rs)x=ls+rs;
else zhuan(x,d),shan(x,val);
}
else t[x].size--,shan(t[x].ch[t[x].val<val],val);
}
int rank(int x,int val){//k的排名
if(!x)return 0;
if(t[x].val==val)return t[ls].size+1;
if(t[x].val>val)return rank(ls,val);
return rank(rs,val)+t[ls].size+t[x].cnt;
}
int kth(int root,int k){//k大
int x=root;
while(1){
if(k<=t[ls].size)x=ls;
else if(k>t[ls].size+t[x].cnt)
k-=t[ls].size+t[x].cnt,x=rs;
else return t[x].val;
}
}
int pre(int x,int val){//前驱
if(!x)return -inf;
if(t[x].val>=val)return pre(ls,val);
return max(pre(rs,val),t[x].val);
}
int nxt(int x,int val){//后继
if(!x)return inf;
if(t[x].val<=val)return nxt(rs,val);
return min(nxt(ls,val),t[x].val);
}
}tr;
int main(){
int n=get(),rt=0;
while(n--){
int q=get(),x=get();
if(q==1)tr.insert(rt,x);
if(q==2)tr.shan(rt,x);
if(q==3)printf("%d\n",tr.rank(rt,x));//注意是rt不是1或0
if(q==4)printf("%d\n",tr.kth(rt,x));
if(q==5)printf("%d\n",tr.pre(rt,x));
if(q==6)printf("%d\n",tr.nxt(rt,x));
}
return 0;
}
我wa的点：
555：
1、主程序中时rt不是0或1
2、读优要带负数！！！！！
完结散花
