https://www.luogu.com.cn/problem/P3369
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x = 0;
bool f = false;
char ch = getchar();
while(ch > '9' || ch < '0')
{
if(ch == '-')
f = true;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return f? -x : x;
}
const int N=1e5+5;
int cnt,rad=12,rt;
int val[N],sl[N],sr[N],rd[N],Siz[N];
struct node
{
int x,y;
};
int n,m;
void push_up(int x)
{
Siz[x]=Siz[sl[x]]+Siz[sr[x]]+1;
}
node split(int x,int k)
{
if(!x) return {0,0};
if(val[x]<k)
{
node t=split(sr[x],k);
sr[x]=t.x;
push_up(x);
return {x,t.y};
}
else
{
node t=split(sl[x],k);
sl[x]=t.y;
push_up(x);
return {t.x,x};
}
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
if(rd[x]<rd[y])
{
sr[x]=merge(sr[x],y);
push_up(x);
return x;
}
else
{
sl[y]=merge(x,sl[y]);
push_up(y);
return y;
}
}
void insert(int x)
{
rad*=20120913;
cnt++;
val[cnt]=x,rd[cnt]=rad,Siz[cnt]=1;
node t=split(rt,x);
rt=merge(merge(t.x,cnt),t.y);
}
void eraser(int x)
{
node a=split(rt,x-1);
node b=split(a.y,x);
b.x=merge(b.x,b.y);
rt=merge(a.x,merge(b.x,b.y));
}
int jhd(int x)
{
int ans;
node t=split(rt,x);
ans=Siz[t.x]+1;
rt=merge(t.x,t.y);
return ans;
}
int wzh(int k)
{
int pos=rt;
while(pos)
{
if(k==Siz[sl[pos]]+1) return val[pos];
if(k<=Siz[sl[pos]]) pos=sl[pos];
else k-=Siz[sl[pos]]+1,pos=sr[pos];
}
}
int jwl(int x)
{
return wzh(jhd(x)-1);
}
int trj(int x)
{
return wzh(jhd(x+1));
}
int main()
{
m=read();
while(m--)
{
int op,x;
op=read(),x=read();
if(op==1) insert(x);
if(op==2) eraser(x);
if(op==3) printf("%d\n",jhd(x));
if(op==4) printf("%d\n",wzh(x));
if(op==5) printf("%d\n",jwl(x));
if(op==6) printf("%d\n",trj(x));
}
return 0;
}