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,求大佬们指教