Splay 60pts

WA #6~#10

都在几百行挂掉的

菜鸡找不到bug麻烦大犇们康康

#include<bits/stdc++.h>
#define re register 
#define mod 998244353
#define N 100010
#define inf 10000005
#define eps (1e-10)
#define int long long
using namespace std;
int n,m,rt,tot,ans;
int fa[N],lc[N],rc[N],val[N],size[N];
template <class T> inline void read(T &x)
{
	x=0;int g=1;char ss=getchar();
	for (;ss>'9'||ss<'0';ss=getchar()) if (ss=='-') g=-1;
	for (;ss<='9'&&ss>='0';ss=getchar()) x=(x<<1)+(x<<3)+(ss^48);	
	x*=g;
} 
inline void update (int x)
{
	size[x]=size[lc[x]]+size[rc[x]]+1;
}
inline void rotate(int x)
{
	int y=fa[x];int z=fa[y];
	int b=(lc[y]==x)?rc[x]:lc[x];
	fa[x]=z;fa[y]=x;
	if (b)	fa[b]=y;
	if (z) (y==lc[z]?lc[z]:rc[z])=x;
	if (x==lc[y]) rc[x]=y,lc[y]=b;
	else	lc[x]=y,rc[y]=b;
	update(y);update(x); 
}
inline bool wrt(int x)
{
	return rc[fa[x]]==x;
} 
void splay(int x,int tar)
{
	while(fa[x]!=tar)
	{
		if (fa[fa[x]]!=tar)
			wrt(x)==wrt(fa[x])?rotate(fa[x]):rotate(x);
		rotate(x);
	}
	if (!tar) rt=x;
}
void insert(int v)
{
	int x=rt,y=0,dir;
	while(x)
	{
		++size[y=x];
		if (v<val[x]) dir=0,x=lc[x];
		else dir=1,x=rc[x];
	}
	x=++tot;
	fa[x]=y;val[x]=v;size[x]=1;
	if (y) (dir==0?lc[y]:rc[y])=x;
	splay(x,0);
}
void join(int u,int v)
{
	fa[u]=fa[v]=0;
	int w=u;
	while(rc[w]) w=rc[w];
	splay(w,0);
	rc[w]=v;fa[v]=w;
}
void dele(int x)
{
	splay(x,0);
	if (!lc[x]||!rc[x])
		fa[rt=lc[x]+rc[x]]=0;
	else join(lc[x],rc[x]);
	lc[x]=rc[x]=0;
}
int find(int v)
{
	int x=rt;
	while(x)
	{
		if (v==val[x]) break;
		if (v>val[x]) x=rc[x];
		else x=lc[x];
	}
	if (x) splay(x,0);
	return x;
}
int getrank(int v)
{
	int x=find(v);
	return size[lc[x]]+1;
}
int getval(int v)
{
	int x=rt;
	while(1)
	{
		if (lc[x]&&size[lc[x]]>=v)	x=lc[x];
		else
		{
			v-=size[lc[x]]+1;
			if (v<=0) {splay(x,0);return val[x];}
			x=rc[x];
		}
	}
}

int getlst(int v)
{
	int x=rt;
	int res=-inf; 
	while(x)
	{
		if (val[x]<v&&val[x]>=res) res=val[x];
		if (val[x]<v) {if (rc[x]) x=rc[x];else break;} 
		else  {if (lc[x]) x=lc[x];else break;}
	}
	splay(x,0);
	return res;
}
int getnxt(int v)
{
	int x=rt;
	int res=inf; 
	while(x)
	{
		if (val[x]>v&&val[x]<=res) res=val[x];
		if (val[x]>v) {if (lc[x]) x=lc[x];else break;} 
		else  {if (rc[x]) x=rc[x];else break;}
	}
	splay(x,0);
	return res;
}
signed main()
{
	re int i,j,x,y,z,op;
	read(m);
	while(m--)
	{
		read(op);read(x);
		if (op==1)	insert(x);
		else if (op==2) dele(find(x));
		else if (op==3)	ans=getrank(x);
		else if (op==4)	ans=getval(x);
		else if (op==5) ans=getlst(x);
		else ans=getnxt(x);
		if (op>2) printf("%lld\n",ans);
	}
	return 0;
}