\(treap\)
基本操作
简述
\(treap\)将二叉搜索树和堆结合在一起
为维护深度，给每个节点随机分配权值\(dat\)，如下
struct tree{int s[2],vl,dt,ct,sz;}t[N];
il void upd(cs int &i){
t[i].sz=t[i].ct+t[t[i].s[0]].sz+t[t[i].s[1]].sz;
return;
}
在维护查询值\(val\)满足二叉搜索树结构的同时，让\(dat\)满足小根堆结构（也可以是大根堆，不过我写的小根堆）
怎么让\(dat\)满足小根堆呢，这里我们引入旋转操作\(rotate\)
\(rotate\)
旋转操作分为两种
左旋\(zag\)：将\(i\)旋到左儿子（\(i\)的右儿子向左旋转至\(i\)）
il void zag(int &i){
int o=t[i].s[1];
t[i].s[1]=t[o].s[0];
t[o].s[0]=i,t[o].sz=t[i].sz;
return upd(i),i=o,void();
}
右旋\(zig\)：将\(i\)旋到右儿子（\(i\)的左儿子向右旋转至\(i\)）
il void zig(int &i){
int o=t[i].s[0];
t[i].s[0]=t[o].s[1];
t[o].s[1]=i,t[o].sz=t[i].sz;
return upd(i),i=o,void();
}
发现\(zag\)和\(zig\)的实现很像，于是可以写在一起（多传一个参数表示方向就可以了）
il void rtt(int &i,cs bool d){//d表示方向，d=0:zag d=1:zig
int o=t[i].s[d^1];
t[i].s[d^1]=t[o].s[d];
t[o].s[d]=i,t[o].sz=t[i].sz;
return upd(i),i=o,void();
}
（因为\(treap\)总是把\(i\)往下旋，所以不用维护父指针）
关于什么时候需要\(rotate\)，下面操作中再说
\(insert\)
to be continue~
il int add(cs int &x){
t[++id].vl=x,t[id].dt=srd(),t[id].sz=t[id].ct=1;
t[id].s[0]=t[id].s[1]=0;return id;
}
il void ins(int &i,cs int &x){
if(!i) return i=add(x),void();
else t[i].sz++;
if(t[i].vl==x) t[i].ct++;
else{
bool d=(t[i].vl<x);
ins(t[i].s[d],x);
if(t[t[i].s[d]].dt<t[i].dt) rtt(i,d^1);
}
return;
}
\(delete\)
to be continue~
il void del(int &i,cs int &x){
if(t[i].vl==x){
if(t[i].ct>1) t[i].ct--,t[i].sz--;
else if(!(t[i].s[0]*t[i].s[1])) i=t[i].s[0]+t[i].s[1];
else{
bool d=(t[t[i].s[0]].dt<t[t[i].s[1]].dt);
rtt(i,d),del(i,x);
}
return;
}t[i].sz--;
return del(t[i].s[(x>t[i].vl)],x);
}
查询数\(x\)的排名
to be continue~
il int rnk(cs int &x){
ri int i=rt,rk=1;
while(i){
if(x==t[i].vl) return rk+t[t[i].s[0]].sz;
if(x<t[i].vl) i=t[i].s[0];
else rk+=t[t[i].s[0]].sz+t[i].ct,i=t[i].s[1];
}
return rk;
}
查询排名为\(x\)的数
to be continue~
il int kth(int x){
ri int i=rt;
while(i){
if(t[t[i].s[0]].sz<x&&t[t[i].s[0]].sz+t[i].ct>=x) return t[i].vl;
if(t[t[i].s[0]].sz>=x) i=t[i].s[0];
else x-=t[t[i].s[0]].sz+t[i].ct,i=t[i].s[1];
}
return 0;
}
查询数\(x\)的前驱
to be continue~
il int pre(cs int &x){
ri int i=rt,as=-inf;
while(i){
if(t[i].vl<x) as=t[i].vl,i=t[i].s[1];
else i=t[i].s[0];
}
return as;
}
查询数\(x\)的后继
to be continue~
il int nxt(cs int &x){
ri int i=rt,as=inf;
while(i){
if(t[i].vl>x) as=t[i].vl,i=t[i].s[0];
else i=t[i].s[1];
}
return as;
}
to be continue~
code
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
using namespace std;
namespace x314{
il int rd(){
ri int x=0,f=1;ri char c=getchar();
while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
return x*f;
}
short tl=0,wr[20];
il void wt(int x){
if(x<0) x=-x,putchar('-');
do wr[++tl]=x%10,x/=10; while(x);
while(tl) putchar(wr[tl--]+48);
putchar('\n'),tl=0;
}
cs int N=1e5+5,inf=1e9+7;int rt,id;mt19937 srd(time(0));
struct tree{int s[2],vl,dt,ct,sz;}t[N];
il void upd(cs int &i){
t[i].sz=t[i].ct+t[t[i].s[0]].sz+t[t[i].s[1]].sz;
return;
}
il void rtt(int &i,cs bool d){//1zig 0zag
int o=t[i].s[d^1];
t[i].s[d^1]=t[o].s[d];
t[o].s[d]=i,t[o].sz=t[i].sz;
return upd(i),i=o,void();
}
il int add(cs int &x){
t[++id].vl=x,t[id].dt=srd(),t[id].sz=t[id].ct=1;
t[id].s[0]=t[id].s[1]=0;return id;
}
il void ins(int &i,cs int &x){
if(!i) return i=add(x),void();
else t[i].sz++;
if(t[i].vl==x) t[i].ct++;
else{
bool d=(t[i].vl<x);
ins(t[i].s[d],x);
if(t[t[i].s[d]].dt<t[i].dt) rtt(i,d^1);
}
return;
}
il void del(int &i,cs int &x){
if(t[i].vl==x){
if(t[i].ct>1) t[i].ct--,t[i].sz--;
else if(!(t[i].s[0]*t[i].s[1])) i=t[i].s[0]+t[i].s[1];
else{
bool d=(t[t[i].s[0]].dt<t[t[i].s[1]].dt);
rtt(i,d),del(i,x);
}
return;
}
return t[i].sz--,del(t[i].s[(x>t[i].vl)],x);
}
il int rnk(cs int &x){
ri int i=rt,rk=1;
while(i){
if(x==t[i].vl) return rk+t[t[i].s[0]].sz;
if(x<t[i].vl) i=t[i].s[0];
else rk+=t[t[i].s[0]].sz+t[i].ct,i=t[i].s[1];
}
return rk;
}
il int kth(int x){
ri int i=rt;
while(i){
if(t[t[i].s[0]].sz<x&&t[t[i].s[0]].sz+t[i].ct>=x) return t[i].vl;
if(t[t[i].s[0]].sz>=x) i=t[i].s[0];
else x-=t[t[i].s[0]].sz+t[i].ct,i=t[i].s[1];
}
return 0;
}
il int pre(cs int &x){
ri int i=rt,as=-inf;
while(i){
if(t[i].vl<x) as=t[i].vl,i=t[i].s[1];
else i=t[i].s[0];
}
return as;
}
il int nxt(cs int &x){
ri int i=rt,as=inf;
while(i){
if(t[i].vl>x) as=t[i].vl,i=t[i].s[0];
else i=t[i].s[1];
}
return as;
}
} using namespace x314;
int main(){
int n=rd();
for(ri int i=1,op,x;i<=n;++i){
op=rd(),x=rd();
if(op==1) ins(rt,x);
if(op==2) del(rt,x);
if(op==3) wt(rnk(x));
if(op==4) wt(kth(x));
if(op==5) wt(pre(x));
if(op==6) wt(nxt(x));
}
return 0;
}