不懂就问
查看原帖
不懂就问
585805
MCRS_lizi楼主2023/1/17 11:08

首先这是我已经通过的提交记录

但是很明显我的 splay 函数和 rotate 函数是从题解上复制下来的。毕竟作为一名初学者我需要从各种不同版本的题解进行学习。

但是我如果使用 OI wiki 中的相关函数连样例都过不去,如下:

inline void Rotate(int x) {
  int y = f[x], z = f[y], k = Get(x);
  if (!isRoot(y)) ch[z][ch[z][1] == y] = x;
  // 上面这句一定要写在前面,普通的 Splay 是不用的,因为 isRoot  (后面会讲)
  ch[y][k] = ch[x][!k], f[ch[x][!k]] = y;
  ch[x][!k] = y, f[y] = x, f[x] = z;
  PushUp(y), PushUp(x);
}

inline void Splay(int x) {
  Update(x);  // 马上就能看到啦。在 Splay 之前要把旋转会经过的路径上的点都 PushDown
  for (int fa; fa = f[x], !isRoot(x); Rotate(x)) {
    if (!isRoot(fa)) Rotate(Get(fa) == Get(x) ? fa : x);
  }
}

变量名与函数名的差异忽略,请问是为什么?

2023/1/17 11:08
加载中...