RT,我是用splay过的这题。代码里的 rotate 函数是这样写的:
inline void rotate(int x){
int y=fa[x],z=fa[y],sx=son(x),sy=son(y),b=ch[x][!sx];
push_down(y);push_down(x);
if(z) ch[z][sy]=x; else root=x;fa[x]=z;
ch[x][!sx]=y;fa[y]=x;
ch[y][sx]=b;if(b) fa[b]=y;
push_up(y);push_up(x);
}
很显然push_down(y) 会改变 ch[x][!sx] 的值,因此它应该放到 b=ch[x][!sx] 的前面才对。但我按照上面所写的代码通过了本题,那么到底是本题数据过水还是另有原因?求巨佬解答,万分感谢!