社区讨论

难道我的splay写成了spaly?

P2286[HNOI2004] 宠物收养场参与者 8已保存回复 21

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
21 条
当前快照
1 份
快照标识符
@mi7ytg7s
此快照首次捕获于
2025/11/21 05:50
4 个月前
此快照最后确认于
2025/11/21 06:52
4 个月前
查看原帖
照理来讲此题用splay应该跑得非常迅速qwq
但是我丑陋的splay却必须吸一口氧才能活下来
所以为啥呢qwq,请大佬调一下错吧,splay代码已经封装好放在下面了
C
struct splay_balanceBST
{
	vector<int> bin;
	int root,son[N][2],siz[N],fa[N],val[N],cnt[N],tl;
	inline int chk(int tmp)
	{
   		return son[fa[tmp]][1]==tmp;
	}
	inline void up(int tmp)
	{
 		siz[tmp]=siz[son[tmp][0]]+siz[son[tmp][1]]+cnt[tmp];
	}
	inline void rotate(int tmp)
	{
    	int f=fa[tmp],grf=fa[f];
    	int p=chk(tmp),q=p^1;
    	son[f][p]=son[tmp][q],fa[son[tmp][q]]=f;
    	son[grf][chk(f)]=tmp,fa[tmp]=grf;
    	son[tmp][q]=f,fa[f]=tmp;
    	up(f),up(tmp);
	}
	inline void splay(int tmp,int aim)
	{
    	while(fa[tmp]!=aim)
   		{
      		int f=fa[tmp],grf=fa[f];
      		if(grf!=aim&&chk(tmp)==chk(f)) rotate(f);
        	else rotate(tmp);
    	}
    	if(!aim) root=tmp;
	}
	inline void tort(int tmp)
	{
    	int cur=root;
    	while(son[cur][tmp>val[cur]] && tmp!=val[cur]) cur=son[cur][tmp>val[cur]];
    	splay(cur,0);
	}
	inline void ins(int tmp)
	{
    	int cur=root,fnp=0;
    	while(cur && tmp!=val[cur]) fnp=cur,cur=son[cur][tmp>val[cur]];
    	if(cur) siz[cur]++,cnt[cur]++;
    	else
    	{
        	if(bin.empty()) cur=++tl;
        	else cur=bin[bin.size()-1],bin.pop_back();
        	if(fnp) son[fnp][tmp>val[fnp]]=cur;
        	val[cur]=tmp;
        	fa[cur]=fnp,siz[cur]=1,cnt[cur]=1;
        	son[cur][0]=son[cur][1]=0;
    	}
    	splay(cur,0);
	}
	inline int prepos(int tmp)
	{
    	tort(tmp);
    	if(val[root]<tmp) return root;
    	int cur=son[root][0];
    	while(son[cur][1]) cur=son[cur][1];
    	splay(cur,0);
    	return cur;
	}
	inline int succpos(int tmp)
	{
    	tort(tmp);
    	if(val[root]>tmp) return root;
    	int cur=son[root][1];
    	while(son[cur][0]) cur=son[cur][0];
    	splay(cur,0);
    	return cur;
	}
	inline void del(int tmp)
	{
    	int pr=prepos(tmp),suc=succpos(tmp);
    	splay(pr,0),splay(suc,root);
    	int aim=son[suc][0];
    	if(!aim) return;
    	else if(cnt[aim]==1)
    	{
        	bin.push_back(aim);
        	son[suc][0]=0;
    	}
    	else
    	{
        	cnt[aim]--,siz[aim]--;
        	splay(aim,0);
    	}
	}
} pet,peo;

回复

21 条回复,欢迎继续交流。

正在加载回复...