rt,从 P3369 蒯过来的能 AC 代码在这里 WA 了/kk,不知道为什么
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=2e5+51,inf=0x3f3f3f3f;
ll n,op,x;
inline ll read()
{
register ll num=0,neg=1;
register char ch=getchar();
while(!isdigit(ch)&&ch!='-')
{
ch=getchar();
}
if(ch=='-')
{
neg=-1;
ch=getchar();
}
while(isdigit(ch))
{
num=(num<<3)+(num<<1)+(ch-'0');
ch=getchar();
}
return num*neg;
}
namespace Splay{
struct Node{
ll fa,val,sz,tmp;
ll ch[2];
inline void reset(ll val=0,ll fa=0)
{
this->val=val,this->fa=fa,this->sz=this->tmp=1;
this->ch[0]=this->ch[1]=0;
}
};
struct Splay{
ll tot,rt;
Node nd[MAXN];
inline ll id(ll x)
{
return nd[nd[x].fa].ch[1]==x;
}
inline void update(ll x)
{
nd[x].sz=nd[nd[x].ch[0]].sz+nd[nd[x].ch[1]].sz+nd[x].tmp;
}
inline void connect(ll x,ll fa,ll dir)
{
nd[x].fa=fa,nd[fa].ch[dir]=x;
}
inline void rotate(ll x)
{
ll fa=nd[x].fa,gfa=nd[fa].fa,dir=id(x);
connect(x,gfa,id(fa));
connect(nd[x].ch[dir^1],fa,dir);
connect(fa,x,dir^1);
update(fa),update(x);
}
inline void splay(ll cur,ll target)
{
while(nd[cur].fa!=target)
{
ll fa=nd[cur].fa,gfa=nd[fa].fa;
if(gfa!=target)
{
rotate(id(cur)^id(fa)?cur:fa);
}
rotate(cur);
}
rt=target?rt:cur;
}
inline void insert(ll val)
{
ll x=rt,fa=0;
while(x&&nd[x].val!=val)
{
fa=x,x=nd[x].ch[val>nd[x].val];
}
if(x)
{
nd[x].tmp++;
}
else
{
x=++tot;
if(fa)
{
nd[fa].ch[val>nd[fa].val]=x;
}
nd[x].reset(val,fa);
}
splay(x,0);
}
inline void find(ll val)
{
ll x=rt;
if(!x)
{
return;
}
while(nd[x].ch[val>nd[x].val]&&nd[x].val!=val)
{
x=nd[x].ch[val>nd[x].val];
}
splay(x,0);
}
inline ll getPrev(ll val)
{
find(val);
ll x=rt;
if(nd[x].val<val)
{
return x;
}
x=nd[x].ch[0];
while(nd[x].ch[1])
{
x=nd[x].ch[1];
}
return x;
}
inline ll getNext(ll val)
{
find(val);
ll x=rt;
if(nd[x].val>val)
{
return x;
}
x=nd[x].ch[1];
while(nd[x].ch[0])
{
x=nd[x].ch[0];
}
return x;
}
inline ll prev(ll val)
{
return nd[getPrev(x)].val;
}
inline ll next(ll val)
{
return nd[getNext(x)].val;
}
inline void del(ll val)
{
ll prv=getPrev(val),nxt=getNext(val),ls;
splay(prv,0),splay(nxt,prv),ls=nd[nxt].ch[0];
if(nd[ls].tmp>1)
{
nd[ls].tmp--,splay(ls,0);
}
else
{
nd[nxt].ch[0]=0;
}
}
inline ll findRank(ll val)
{
return find(val),nd[nd[rt].ch[0]].sz;
}
inline ll findVal(ll rk)
{
ll x=rt,ls;
if(nd[rt].sz<rk)
{
return 0;
}
while(1)
{
ls=nd[x].ch[0];
if(rk>nd[ls].sz+nd[x].tmp)
{
rk-=nd[ls].sz+nd[x].tmp,x=nd[x].ch[1];
}
else
{
if(rk<=nd[ls].sz)
{
x=ls;
}
else
{
return nd[x].val;
}
}
}
}
};
}
Splay::Splay splay;
int main()
{
splay.insert(inf),splay.insert(-inf),n=read();
for(register int i=0;i<n;i++)
{
op=read(),x=read();
if(op==1)
{
printf("%d\n",splay.findRank(x));
}
if(op==2)
{
printf("%d\n",splay.findVal(x+1));
}
if(op==3)
{
printf("%d\n",splay.prev(x));
}
if(op==4)
{
printf("%d\n",splay.next(x));
}
if(op==5)
{
splay.insert(x);
}
}
}