Splay求调
查看原帖
Splay求调
331947
hegm楼主2023/2/4 07:27

只能过一个点,有一个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;
}
2023/2/4 07:27
加载中...