rt,这个,这个,还有这个,求调QAQ
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#define ls tr[now].lsn
#define rs tr[now].rsn
using namespace std;
struct node
{
int dat,cnt,sz,hp,lsn,rsn;
}tr[1000005];
int rut,top,n,tsk,u;
inline void read(int &x)
{
char c=getchar();x=0;
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-48,c=getchar();
}
int mkn(int k)
{
tr[++top]=(node){k,1,1,rand(),0,0};
return top;
}
void upd(int now)
{
tr[now].sz=tr[now].cnt+tr[ls].sz+tr[rs].sz;
}
void spl(int now,int &x,int &y,int k)
{
if(!now) return (void)(x=y=0);
if(tr[now].dat<=k) x=now,spl(rs,rs,y,k);
else y=now,spl(ls,x,ls,k);upd(now);
}
int mrg(int x,int y)
{
if(!x||!y) return x|y;
if(tr[x].hp<tr[y].hp) return tr[x].rsn=mrg(tr[x].rsn,y),upd(x),x;
else return tr[y].lsn=mrg(x,tr[y].lsn),upd(y),y;
}
void ins(int k)
{
int lft=0,rit=0,mid=0;
spl(rut,lft,rit,k);
spl(lft,lft,mid,k-1);
if(!mid) mid=mkn(k);
else tr[mid].cnt++,tr[mid].sz++;
rut=mrg(mrg(lft,mid),rit);
}
void del(int k)
{
int lft=0,rit=0,mid=0;
spl(rut,lft,rit,k);
spl(lft,lft,mid,k-1);
if(--tr[mid].cnt) tr[mid].sz--,rut=mrg(mrg(lft,mid),rit);
else rut=mrg(lft,rit);
}
int rnk(int k)
{
int lft=0,rit=0,ans=0;
spl(rut,lft,rit,k-1);
ans=tr[lft].sz+1;
rut=mrg(lft,rit);
return ans;
}
int val(int now,int k)
{
if(tr[ls].sz+1<=k&&k<=tr[ls].sz+tr[now].cnt) return tr[now].dat;
if(k<=tr[ls].sz) return val(ls,k);
else return val(rs,k-tr[ls].sz-tr[now].cnt);
}
int pre(int k)
{
int lft=0,rit=0,ans=0;
spl(rut,lft,rit,k-1);
ans=val(lft,tr[lft].sz);
rut=mrg(lft,rit);
return ans;
}
int suf(int k)
{
int lft=0,rit=0,ans=0;
spl(rut,lft,rit,k);
ans=val(rit,1);
rut=mrg(lft,rit);
return ans;
}
int main()
{
srand((long long)new char);
read(n);
while(n--)
{
read(tsk);read(u);
if(tsk==1) ins(u);
else if(tsk==2) del(u);
else if(tsk==3) printf("%d\n",rnk(u));
else if(tsk==4) printf("%d\n",val(rut,u));
else if(tsk==5) printf("%d\n",pre(u));
else printf("%d\n",suf(u));
}
}