无旋treap
柒葉灬
2019-08-21 21:37:17
# 无旋treap
-----
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
int n;
int tot,root;
int son[maxn][2],sz[maxn],val[maxn],rnd[maxn];
int newnode(int x){
sz[++tot]=1;
val[tot]=x;
rnd[tot]=rand();
return tot;
}
void up(int p){
sz[p]=sz[son[p][0]]+sz[son[p][1]]+1;
}
int merge(int a,int b){
if(!a||!b)return a|b;
if(rnd[a]<rnd[b]){
son[a][1]=merge(son[a][1],b);
up(a);
return a;
}else {
son[b][0]=merge(a,son[b][0]);
up(b);
return b;
}
}
void split(int now,int K,int &x,int &y){
if(!now){
x=0,y=0;
return;
}
if(val[now]<=K){
x=now;
split(son[now][1],K,son[now][1],y);
}else {
y=now;
split(son[now][0],K,x,son[now][0]);
}
up(now);
}
void insert(int val){
int x,y;
split(root,val,x,y);
root=merge(merge(x,newnode(val)),y);
}
void del(int val){
int x,y,z;
split(root,val,x,z);
split(x,val-1,x,y);
y=merge(son[y][0],son[y][1]);
root=merge(merge(x,y),z);
}
int Kth(int root,int K){
int x=root;
while(1){
if(sz[son[x][0]]>=K)x=son[x][0];
else if(sz[son[x][0]]+1==K)return val[x];
else K-=sz[son[x][0]]+1,x=son[x][1];
}
}
int Rank(int val){
int x,y;
split(root,val-1,x,y);
int res=sz[x]+1;
root=merge(x,y);
return res;
}
int pre(int val){
int x,y;
split(root,val-1,x,y);
int res=Kth(x,sz[x]);
root=merge(x,y);
return res;
}
int nxt(int val){
int x,y;
split(root,val,x,y);
int res=Kth(y,1);
root=merge(x,y);
return res;
}
int main(){
srand(time(NULL));
cin>>n;
for(int i=1,op,x;i<=n;i++){
scanf("%d%d",&op,&x);
if(op==1){
insert(x);
}else if(op==2){
del(x);
}else if(op==3){
printf("%d\n",Rank(x));
}else if(op==4){
printf("%d\n",Kth(root,x));
}else if(op==5){
printf("%d\n",pre(x));
}else if(op==6){
printf("%d\n",nxt(x));
}
}
return 0;
}
```
-----
可持久化无旋treap
代码
```cpp
#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=5e5+100,maxm=maxn*50,P=998244353;
bool cur1;
int n;
int tot,rt[maxn],son[maxm][2],sz[maxm],val[maxm],rnd[maxm];
int newnode(int x){
val[++tot]=x;
rnd[tot]=rand();
sz[tot]=1;
return tot;
}
int copy(int p){
val[++tot]=val[p];
sz[tot]=sz[p];
rnd[tot]=rand();
son[tot][0]=son[p][0];
son[tot][1]=son[p][1];
return tot;
}
void up(int p){
sz[p]=sz[son[p][0]]+sz[son[p][1]]+1;
}
int merge(int a,int b){
if(!a||!b)return a|b;
if(rnd[a]<rnd[b]){
int p=copy(a);
son[p][1]=merge(son[a][1],b);
up(p);
return p;
}else {
int p=copy(b);
son[p][0]=merge(a,son[b][0]);
up(p);
return p;
}
}
void split(int now,int K,int &x,int &y){
if(!now){
x=y=0;
return;
}
// puts("!@#");
int p=copy(now);
if(val[now]<=K){
x=p;
split(son[p][1],K,son[p][1],y);
up(p);
}else {
y=p;
split(son[p][0],K,x,son[p][0]);
up(p);
}
}
int Kth(int rt,int K){
int u=rt;
while(233){
if(sz[son[u][0]]>=K)u=son[u][0];
else if(sz[son[u][0]]+1==K)return val[u];
else K-=sz[son[u][0]]+1,u=son[u][1];
}
}
int pre(int &rt,int val){
int x,y;
split(rt,val-1,x,y);
int res=Kth(x,sz[x]);
rt=merge(x,y);
return res;
}
int nxt(int &rt,int val){
int x,y;
split(rt,val,x,y);
int res=Kth(y,1);
rt=merge(x,y);
return res;
}
void del(int &rt,int val){
int x,y,z;
split(rt,val,y,z);
split(y,val-1,x,y);
y=merge(son[y][0],son[y][1]);
rt=merge(x,merge(y,z));
}
void insert(int &rt,int val){
int x,y;
split(rt,val,x,y);
rt=merge(merge(x,newnode(val)),y);
}
int Rank(int &rt,int val){
int x,y;
split(rt,val-1,x,y);
int res=sz[x]+1;
rt=merge(x,y);
return res;
}
bool cur2;
int main(){
// double sz=&cur1-&cur2;
// cout<<sz/1024<<endl;
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
srand(20190824);
cin>>n;
insert(rt[0],-2147483647);
insert(rt[0],2147483647);
// debug(sz[rt[0]]);
for(int i=1,t,op,x;i<=n;i++){
scanf("%d%d%d",&t,&op,&x);
rt[i]=rt[t];
if(op==1){
insert(rt[i],x);
}else if(op==2){
del(rt[i],x);
}else if(op==3){
printf("%d\n",Rank(rt[i],x)-1);
}else if(op==4){
printf("%d\n",Kth(rt[i],x+1));
}else if(op==5){
printf("%d\n",pre(rt[i],x));
}else if(op==6){
printf("%d\n",nxt(rt[i],x));
}
}
return 0;
}
```