只能过一个点,有一个WA其余的TLE
#include<bits/stdc++.h>
#define N 200006
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int siz[N],cnt[N],son[N][2],rt,val[N],fa[N],tot,awa;
void up(int now)
{
if(!now)return ;
siz[now]=cnt[now];
if(son[now][1])siz[now]+=siz[son[now][1]];
if(son[now][0])siz[now]+=siz[son[now][0]];
}
int fson(int now){return son[fa[now]][1]==now;}
void link(int x,int y,bool c)
{
fa[y]=x;
son[x][c]=y;
up(y);up(x);
}
void upon(int now)
{
int f=fa[now],g=fa[fa[now]];
bool c=fson(now),b=fson(f);
int s=son[now][!c];//下面要按深度link,保证up的顺序正确
link(f,s,c);link(now,f,!c);link(g,now,b);
}
void splay(int now)
{
for(int i;i;upon(now))
{
if(fa[now]==0)break;
i=fa[now];
if(fa[i]&&fson(now)==fson(i))
upon(i);
}
rt=now;
}
int news(int x)
{
++tot;
siz[tot]=cnt[tot]=1;
val[tot]=x;
return tot;
}
void insert(int x)
{
if(!rt)
{
rt=news(x);
return ;
}
int now=rt,f=0;
while(1)
{
if(x==val[now])
{
cnt[now]++;
up(now);up(f);
splay(now);
break;
}
f=now;
now=son[now][val[now]<x];
if(!now)
{
now=news(x);
link(f,now,val[f]<x);
splay(now);
break;
}
}
}
int rnk(int now,int x)//查询x的排名
{
if(!now)return 0;
if(val[now]==x)
{
awa=now;
return 1;
}
if(val[now]<x)return 1+siz[son[now][0]]+rnk(son[now][1],x);
return rnk(son[now][0],x);
}
int find(int now,int x)//查询排名为x的数
{
if(x<=siz[son[now][0]])return find(son[now][0],x);
if(x>siz[son[now][0]]+cnt[now])
return find(son[now][1],x-siz[son[now][0]]-cnt[now]);
return val[now];
}
int front(int x,int st)//前驱
{
int now=st,ans=0;
while(now)
{
if(val[now]<x)ans=val[now];
now=son[now][val[now]<x];
}
return ans;
}
int tail(int x,int st)//后继
{
int now=st,ans=0;
while(now)
{
if(val[now]>x)ans=val[now];
now=son[now][val[now]<=x];
}
return ans;
}
void del(int x)
{
find(rt,x);
splay(awa);
if(cnt[rt]>1)
{
cnt[rt]--;
up(rt);
return ;
}
if(!(son[rt][0]|son[rt][1]))
{
rt=0;
return ;
}
if(son[rt][1]&&son[rt][0])
{
int pos=front(x,son[rt][1]),ot=rt;
splay(pos);
link(rt,son[ot][1],1);
return ;
}
if(son[rt][1])rt=son[rt][1];
if(son[rt][0])rt=son[rt][0];
fa[rt]=0;
}
int n;
int main()
{
n=read();
for(int i=1,op,x;i<=n;i++)
{
op=read();x=read();
if(op==1)insert(x);
if(op==2)del(x);
if(op==3)cout<<rnk(rt,x)<<"\n";
if(op==4)cout<<find(rt,x)<<"\n";
if(op==5)cout<<front(x,rt)<<"\n";
if(op==6)cout<<tail(x,rt)<<"\n";
}
return 0;
}