Splay关于旋转问题的求助
查看原帖
Splay关于旋转问题的求助
524801
不食嗟来之食楼主2023/3/28 21:22

AC的(题解代码)

void spin(int x,int &mb) {//旋转操作
    int fa=f[x],g=f[fa],t=is(x);
    if(fa==mb) mb=x;
    else son[g][is(fa)]=x;
    f[fa]=x,f[x]=g,f[son[x][t^1]]=fa;
    son[fa][t]=son[x][t^1],son[x][t^1]=fa;
    up(fa),up(x);
}
void splay(int x,int &mb) {//splay操作
    while(x!=mb) {
        if(f[x]!=mb) {
            if(is(x)^is(f[x])) spin(x,mb);
            else spin(f[x],mb);
        }
        spin(x,mb);
    }
}

我的(0分过不了样例的)

void rotate(int x) {
	int fa=f[x],f_f=f[fa],_son=is(x);
	son[fa][_son]=son[x][_son^1];
	if(son[x][_son^1]) f[son[x][_son^1]]=fa;
	son[x][_son^1]=fa;
	if(f_f) son[f_f][son[f_f][1]==fa]=x;
	f[fa]=x,f[x]=f_f;
	up(fa),up(x);
	return ;
}
void splay(int x,int top) {
	while(f[x]!=top) {
		int fa=f[x],f_f=f[fa];
		if(f_f!=top) rotate(is(x)==is(fa)?fa:x);
		rotate(x);
	}
	if(!top) rt=x;
}

只是写法不一样吧,为什么我的过不了qwq,求大佬们指教

2023/3/28 21:22
加载中...