```
//旋转法Treap
#include<bits/stdc++.h>
#define M 100001
#define N 51
#define K 51
#define PI 3.1415926535
#define rd read()
#define ll __int128
#define ull unsigned long long
#define il inline
#define strstr stringstream
#define sh short
#define str string
#define db double
#define lowbit(x) (x&(-x))
#define pf push_front
#define pb push_back
#define ppf pop_front
#define ppb pop_back
#define INF 0x3f3f3f3f
#define mod 1000000007
#define sqr(x) (x)*(x)
#define dist(a,b,c,d) sqrt(sqr(a-c)+sqr(b-d))
#define rep(i,j,k) for(register int i=j;i<=k;++i)
#define rep1(i,j,k) for(register int i=j;i>=k;--i)
#define rep2(i,j,k) for(register int i=j;i<k;++i)
#define rep3(i,j,k) for(register int i=j;i>k;--i)
#define nrep(i,j,k) for(i=j;i<=k;++i)
#define nrep1(i,j,k) for(i=j;i>=k;--i)
#define nrep2(i,j,k) for(i=j;i<k;++i)
#define nrep3(i,j,k) for(i=j;i>k;--i)
#define alpha 0.75
using namespace std;
int n,op,x,root,cnt;
struct node
{
int l,r,val,pri,size;
}t[M];
il void newnode(int val)
{
t[++cnt]={0,0,val,rand(),1};
}
il void update(int now){t[now].size=t[t[now].l].size+t[t[now].r].size+1;}
il void rotate(int &now,bool f)
{
int k;
if(f)
{
k=t[now].r;
t[now].r=t[k].l;
t[k].l=now;
}
else
{
k=t[now].l;
t[now].l=t[k].r;
t[k].r=now;
}
t[k].size=t[now].size;
update(now),now=k;
}
il void ins(int &now,int val)
{
if(now==0){newnode(val);now=cnt;return;}
if(val<t[now].val)ins(t[now].l,val);
else ins(t[now].r,val);
if(t[now].l&&t[t[now].l].pri<t[now].pri)rotate(now,0);
if(t[now].r&&t[t[now].r].pri<t[now].pri)rotate(now,1);
}
il void del(int &now,int val)
{
t[now].size--;
if(t[now].val==val)
{
if(t[now].l==0&&t[now].r==0)now=0;
else if(t[now].l==0||t[now].r==0)now=t[now].l+t[now].r;
else if(t[t[now].l].pri<t[t[now].r].pri)rotate(now,0),del(t[now].r,val);
else rotate(now,1),del(t[now].l,val);
}
if(val<=t[now].val)del(t[now].l,val);
else del(t[now].r,val);
update(now);
}
il int getrank(int val)
{
int rank=1,now=root;
while(now)
{
if(val<=t[now].val)now=t[now].l;
else rank+=t[t[now].l].size+1,now=t[now].r;
}
return rank;
}
il int getnum(int rank)
{
int now=root;
while(now)
{
if(rank==t[t[now].l].size+1)break;
else if(rank<=t[now].size)now=t[now].l;
else rank-=t[t[now].l].size+1,now=t[now].r;
}
return t[now].val;
}
main()
{std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
while(n--)
{
cin>>op>>x;
if(op==1)ins(root,x);
else if(op==2)del(root,x);
else if(op==3)cout<<getrank(x)<<'\n';
else if(op==4)cout<<getnum(x)<<'\n';
else if(op==5)cout<<getnum(getrank(x)-1)<<'\n';
else cout<<getnum(getrank(x+1))<<'\n';
}
return 0;
}
```
by zhanglewei4598 @ 2023-11-11 10:04:23