本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-04 18:43:48

SD-S00524

这位选手，开场 9min，T1 便过了。很好啊！非常好的开局。

快看！这位选手，把 T2 秒了！我去，他大样例挂了！我去，他上厕所了！我去，他上完厕所，冷静思考的结果是写了一个分数类！我去，他写完了分数类，开始调式子了！我去，他大样例过了！我去，怎么已经五点了！我去，不着急，200pts 稳稳一等了。我们接着看 T3。

T3 20pts，很一眼啊！先上个厕所。T3，50pts，很简单啊！先吃个士力架，好吃！我去，大样例调出来过了！我靠，怎么拍挂了！我靠，初值错了！我草，拍过了！拍过了！两千组！这玩意儿好像很好优化，但是不管了！没什么时间了！快写 T4！

T4，先吃个士力架。诶我草真好吃。这是什么鬼题，我去，他怎么连 12pts 暴搜都不会？？我去，他把性质 A 切了！我草，怎么已经六点十五了？？？不急，检查一下。嗯，很没问题啊！继续吃士力架，好吃。

出场！哎呀我去，258，虽然不高，这不是稳稳的一等吗！蓝勾勾有了！

奥，T2 没 #include <vector>，爆零了！

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-06 20:38:49

candies

较小值和较大值，可以看成独立。因为两个极值相等后，就再也不会变化了。那么，我们考虑二分出这 $K$ 次操作能让较小的数全增至 $L$，较大的数减至 $R$。$L\le R$ 时，答案即 $R - L$；否则，只有整个序列的总和是 $n$ 的倍数时极差为零，否则为一。

复杂度 $O(n\log V)$

rcomb

先考虑 $80$ 分的部分分。设 $f(n, i)$ 表示还剩 $n$ 张试卷，第 $i$ 张试卷的期望贡献次数。

那么有转移

$$ \begin{aligned} & f(n, 1) = \frac 1 {n-1} + f(n-1,1) \ & f(n, n) = \frac 1 {n-1} + f(n - 1, n - 1) \ & f(n, i) = \frac 2 {n-1} + \frac{i-1}{n-1} f(n-1,i-1) + \frac{n-i}{n-1} f(n-1,i) \end{aligned} $$

这个复杂度是平方的，能通过 $80$ 分。

对于这个部分分，还有一种思考方向，是设 $f(i, j)$ 表示合并完 $[i, j]$ 区间的期望代价。那么 $$f(i, j) = \sum\limits_{k=i}^j a_k + \frac{1}{j-i} \sum\limits_{k=i}^{j-1} f(i, k) + f(k + 1, j)$$

利用前缀和优化，也可以做到平方。

对于 $100$ 分的数据，考虑拆贡献。每个数到答案的贡献，是上面这个式子转移中的第一个 $\sum$。我们需要知道每个数被包含在了长度为多少的区间。

第 $k$ 个数对答案的贡献，可以考虑它往左边合并的概率。当左边有 $k - 1$ 个数时，有 $k - 1$ 种合并的可能，合并到它的概率是 $\dfrac 1 {k-1}$。右边同理，合并到它的概率是 $\dfrac 1 {n-k}$。当左右操作了一轮后，合并到它的概率增加到 $\dfrac 1 {k-2}$。我们对这个求和，就可以了。

最终的复杂度是 $O(n)$。

game

考虑一个暴力。不妨令 $x_1$ 属于 $A$，我们枚举它和哪个 $y$ 对应，就知道 $A$ 的命令。然后去掉所有可以满足 $A$ 命令的人，看看剩下的人是不是合法。这个可以做到 $O(nV)$。

然后利用 bitset 压位优化。复杂度 $O(\dfrac {nV} w)$

p.s. 这玩意儿假了

tree

我们发现用传统的 dfn 序似乎很难做这个东西。因此考虑相对不常用的欧拉序。

欧拉序上一段区间，是树上的一段路径。同时，两个端点的 LCA，就是这段路径上深度最小的点。在此题里，我们可以维护每个点到根的路径长度。那么由于边权非负，LCA 就是到根最近的那个点。

然后，操作一可以转化为子树的修改，因为修改这条边会让子树内到根的路径加上边权增量。

操作二就是查询 $u \in [s_x, e_x]$ 和 $v \in [s_y, e_y]$ 的 $dis_u + dis_v - 2dis_{c}$ 的最大值，其中 $c$ 是 $u, v$ 的 LCA。由刚才的讨论，我们知道 $c$ 就是 $u, v$ 欧拉序区间内的 $\rgmin dis$。

然后考虑操作三。注意到一个性质，即我们只会取两个端点之一。可以考虑如果不取到端点，调整到其中一个端点，路径长度不减。因此，我们就转化为子树到某个点的最远距离。这和操作二可以用相同的方法。

这个东西看起来还是有点吓人。令 $l, m, r$ 分别代表 $dis_u, dis_c, dis_v$，那么我们用线段树维护区间内 $l, m, r, l + m, m + r, l + m + r$ 的最值。这个是经典的。

然后我们考虑 $[s_x, e_x]$ 和 $[s_y, e_y]$ 的交集情况，讨论 $m$ 在左边还是右边即可。复杂度 $O(n\log n)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-07 14:31:12

我们设 $f(x, y, S)$ 表示当前在 $(x, y)$，包含了的宝藏是 $S$，最少的移动步数。那么答案是 $\max val_S - f(x, y, S)$。

考虑转移。前两维的转移是简单的。由于转移顺序不确定，可以最短路。后面的 $S$ 怎么动态维护？

计算几何中的射线法，可以用来判断某个点是否在某个多边形中。具体的方法是：从这个点做一条直线，看其经过这个多边形的多少条边。如果经过奇数条即是在内，否则在外。我们可以沿用相同的方法，每次转移时从每个宝藏平行向右做一条直线，看是否和新扩展出的点交。若交了，则其在 $S$ 中取异或。

这样用最短路转移即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-11 12:39:34

本题有一个非常好的性质：没强制在线。所以我们可以离线下来搞。

具体怎么做呢？本题的核心就是点修、区间第 $k$ 大、区间求排名。我们知道，CDQ 分治和整体二分分别可以很方便并且快速地解决区间排名以及区间第 $k$ 大问题。那么我们分别用这两种算法做不同的操作就可以了。

还剩下前驱和后继，怎么处理？某个数的前驱，可以先算出严格小于这个数的数量 $k$，然后求第 $k$ 大。某个数的后继，可以算出小于等于这个数的数量 $k$，然后求第 $k + 1$ 大。

这时我们发现，我们需要将这两个操作组合起来。我们可以把询问拆开，先跑 CDQ 分治，得到 $k$，然后再跑整体二分，得到最后的结果。

实现起来细节不特别多，主要是主函数中拼接操作的部分不怎么好写。

但是跑起来飞快，没怎么卡常就跑到最优解第二页。

代码

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-18 10:46:01

$nk^2$ 显然。考虑优化。

转移有两种，一种是 $r_k \lt l_i$ 的，转移是 dp[k][j - i + k + 1] + r[i] - l[i]。

另一种是 $r_k \ge l_i$ 的，转移是 dp[k][j - i + k + 1] - r[k] + r[i]。

由于我们把包含的区间删掉了，因此 $l$ 随 $r$ 增。因此，我们可以用单调队列维护第二种转移的最大值。从队头弹的时候，我们知道这个点会变成第一种转移，维护一个最大值就好了。

但是，我们状态的第二维怎么处理？第二维是 $j - i + 1 + k$，因此我们可以对于每一个 $j - i + 1$，维护出 dp[k][k + t] 的最大值，放到 $n$ 个单调队列中即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-18 17:26:40

贪心是显然的，按照右端点排序，同时维护一个堆存放每间教室的最后一场活动结束时间。每次看能不能放进去，能放就尽量放。这个贪心是经典的。

只有所有的教室都占用了，我们才会开新教室用。因此，我们可以二分出来 $mn_i$，表示 $i$ 一定会用的最少教室数量。显然算出 $mn$ 我们就做完了。

单次二分的过程，是我们模拟这个贪心过程，看看这个位置会不会选到。考虑整体二分。

整体二分到值域区间 $[L, R]$ 区间时，我们要看哪些点的 $mn$ 小于等于 $mid$。可以通过线段树区间加，看区间最大值是否小于 $mid$。

好牛逼的题

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-21 10:06:09

KM 算法解决的是二分图带权最大完美匹配问题。

权均为一的时候，贪心地尽量匹配是最优的，因为只要匹配了，带来的收益都一样。但如果权不同，就无法简单贪心了。

我们引入顶标的概念。每个点有一个顶标，记为 $d_x$。一组可行顶标，需要满足 $d_x + d_y \ge w_{xy}$。我们再定义，一个顶标生成一张相等子图，其中包含所有点，以及满足 $d_x + d_y = w_{xy}$ 的所有边。

顶标有什么用？有一个性质，即：如果一组可行顶标生成的相等子图中有一个完美匹配，那么这就是原图的最大权完美匹配。

这是因为相等子图中的边都是使得 $d_x + d_y = w_{xy}$ 的，而原图的边是 $d_x + d_y \ge w_{xy}$。只要相等子图中有完美匹配，其权一定是最大的。

那么，我们现在的问题就是，选择一组合适的可行顶标，使得其生成的相等子图中有最大匹配。我们不妨先构造任意的顶标，随后调整它。

先让最开始每个右部点的顶标为零，每个左部点的顶标，为它所连的边的最大权。这样，最开始的相等子图就是最大权的那些边。在这张相等子图中跑匈牙利算法，看可否得到完美匹配。

如果得不到，我们就要调整顶标。可以将左部点顶标增加 $d = \min \{d_x + d_y - w_{xy}, d_x + d_y \gt w_{xy}\}$，右部点减少这个量。这样，我们保证了增加至少一条边，同时原来的边保存，而且增量也尽可能小。然后我们重复跑最大匹配，直到找到完美匹配。

这个复杂度最差是 $O(n^4)$。考虑优化。我们发现，每次加边时，原来的交错树依旧可用。可以改用 BFS，每次扩展新点时候只是入队，不从头增广。复杂度是 $O(n^3)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-23 16:49:12

要求

$${n\choose m} \bmod p$$

其中 $2 \le p \le 10^6$，$1 \le n, m \le 10^{18}$。$p$ 不一定是质数。

如果 $p$ 是质数，我们可以直接用卢卡斯定理求解。

考虑将 $p$ 分解，然后解出 $n\choose m$ 模 $p$ 的某个质因子次幂的值，最后用 CRT 合并。

那么问题转化为求 ${n\choose m} \bmod p^k$。

拆组合数定义，即 $\dfrac {n!}{m!(n-m)!}$。由于逆元不一定存在，不能直接计算。

考虑计算 $\dfrac {n!} {p^k}$，其中 $k$ 是最大的整数使得 $p^k \mid n!$。然后得到原式为 $\dfrac {n!p^{k1-k2-k3}}{m!(n-m)!} \bmod p^k$。把指数拆出来，就可以求逆元了。

现在的问题是，求 $\dfrac {n!} {p^k}$，也就是把 $1$ 到 $n$ 中 $p$ 的倍数全部抛除，计算剩下的数的乘积。

$p$ 的倍数的乘积是 $\lfloor \dfrac n p\rfloor p^{\lfloor \frac n p\rfloor}$。

不是 $p$ 的倍数的部分，由于 $p^k \le 10^6$，可以按照 $p^k$ 分成许多块，每一块的乘积都是 $\prod\limits_{i=1,(i,p)=1}^{p^k} i$。最后剩下的散块，可以直接暴力。

然后可以根据逆元计算模 $p^k$ 的组合数，之后用 CRT 合并解。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-27 17:46:48

山东提供的是 Windows + NOI Linux 虚拟机。使用 Linux 主要是为了测试编译、时间与内存限制。

传输文件

首先打开终端。按 Super 键（Windows 键）打开搜索框，搜索 terminal 并运行，打开的是一个深紫色背景窗口。

把文件复制到主文件夹，类比 Windows 中的用户目录。在终端中，可以用 ls 命令查看当前文件夹内有哪些文件，检查代码是否复制错了地方。

我在我的工作目录下输入 ls，会得到类似这样的信息：

蓝色的是目录、绿色的是可执行文件，白色的是普通文件。因为我的系统是日用的，所以和考场中有的文件夹不同。一般的，看到有 Documents、Desktop，或者 文档、桌面 等文件夹，就是主目录。

编译源代码

要编译 a.cpp ，可以输入命令：

g++ a.cpp -o a -Wall -Wextra -std=c++14 -O2 -g

其中，g++ 是必须的；a.cpp 是文件名，可以更改；-o a 是指定可执行文件名，Linux 下的可执行文件是不带后缀名的；-Wall -Wextra 是打开所有警告；-std=c++14 是指定标准；-O2 是打开优化，可以删掉；-g 是打开调试符号，不会使用调试器的可以忽略。

运行测试

编译后，可以用 ls 命令查看是否多出来了 a 文件，即指定的可执行文件名。随后，使用 .\/a 命令可以运行这个程序。

以 A + B 为例。我这里的源代码名为 c.cpp，我希望它编译成 c。使用如下命令并运行、输入，得到期望输出：

如果运行编译命令后出现额外信息，是编译错误或者警告，具体和 Dev C++ 下栏中显示的错误相同。比如我将 cin >> a >> b 误写作 cin >> a >> c，会得到：

我们看看 RE 会怎么样。如下图：

我们故意 RE。

Segmentation fault，或者 段错误，是内存访问越界，或者 STL 容器的使用出错。删掉 cout << q[0] << '\n'，看看除零：

会显示 Floating point exception，或 浮点错误 等。有的 STL 错误还会附带 STL 的错误信息，这点和 Windows 是大体一致的。

测试用时

测试程序用时，可以用 time 或者 \/bin\/time 命令，后者显示的更多，不会的可以只用前者。具体的，使用 time .\/a 命令运行并测速，其他的和不测速时一样。由于用键盘输入的时间计入总时，所以最好使用文件输入。

我们以测速 .\/c 为例。这里我用了文件输入输出。

这里我测试了两次，分别是同一份源代码，O2 与不开启 O2 的速度。测评时间是 user 行后面的。这里是 0.104s（O2）与 0.258s（无优化）。

测试内存

内存分为静态内存和动态的。静态的是直接开的全局数组、变量、还有代码本身的长度。动态的如 vector、栈等 STL 容器。

静态内存可以用 size 命令测试。

找到输出的 dec，也就是倒数第三个，6408903，就是静态内存占用，单位是字节。除以 1048576 得到以 MB 为单位的静态内存。

动态内存不好直接测试，但是可以通过限制总内存使用量来判断是否超过内存限制。具体命令是：ulimit -v X，其中 X 是内存限制，单位是 KB。或者，可以使用 ulimit -v $((X * 1024))，X 同样是内存限制，但单位是 MB。记不住可以计算器换算后用前者。

以下面程序为例。

笔算可知内存占用是大概是 380MB。我们把内存放到 256MB：

ulimit 命令前，执行是正常的。执行 ulimit 命令后，我们发现出现 RE。这是因为 MLE 了。

注意内存限制如果过小，会导致终端的正常任务无法执行。这时打开一个新终端即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-04 21:10:21

整理了一些关于 Splay 的资料，一个简洁美丽而高效的数据结构。

Splay 是最简洁的平衡树之一，支持维护区间信息。相比线段树，其可以动态地删点、加点，更加灵活；相比分块，其复杂度是均摊对数，更加高效。

在形态变化时，Splay 并不通过维护一系列性质来保证树高，而是通过伸展保证均摊复杂度。这让它少了常见平衡树的繁杂分讨，但常数也要大不少。

形态及操作

Splay 首先是一棵二叉搜索树，由许多节点组成。我们在每个节点维护父亲的左右儿子指针，以及键值。如有需要，还可以维护它子树内的信息，如它的子树大小。维护子树大小，可以实现快速查询第 k 大或者某数排名。

Splay 的核心操作是伸展（splay）。伸展某个节点 $x$，意味着将 $x$ 节点提升到根，同时更新所维护的子树信息。原来的根在伸展后成为某个普通内部节点。伸展操作的均摊复杂度是对数。

如果能够实现伸展操作，就可以方便地进行许多操作：

• 插入。插入与普通二叉树的插入相同，按照二叉树的遍历方法找到某个叶子节点，将新值插入到该叶子的儿子下。不同的是，在插入某个点后，为了保证复杂度正确，我们要将这个节点伸展到根。

• 删除。首先将这个节点伸展到根，然后将其与其儿子断开。这时原树分裂成两个子树，考虑合并它们。找到左子树的最大值，由二叉树的性质，这个数一定小于右子树的最小值。因此，我们将 $y$ 伸展到根。这时 $y$ 的右儿子一定空，于是将右子树拼到其右儿子上即可。

• 查找某个数。按照二叉树的查找方法，一直找到这个数，或者某个叶子。将最后找到的节点伸展到根。

• 查询排名。首先查找这个数，伸展到根。然后小于其的数数量就是现在根左子树的大小。如果待查询的值不存在，还要考虑根是否小于这个数。

• 查询第 $k$ 大。和二叉树相同。从根节点开始遍历。如果当前节点 $x$ 左子树的大小，也就是小于 $x$ 的数字数量，大于等于 $k$，要找的节点在左子树；如果等于 $k - 1$，那么就是当前节点 $x$；否则，在右子树，并且 $k$ 减去左子树加上当前点大小。

• 查询前驱。伸展到根，然后找左子树的最大值，也就是一直向右走。如果查询的值不存在，特判根是否小于待查值。

• 查询后继。与查询前驱同。

• 查询区间。设待查询区间为 $[l, r]$，我们将 $l - 1$ 旋到根，$r + 1$ 旋到根的右儿子，那么根的右儿子的左儿子，其上的信息就是 $[l, r]$ 的信息。

伸展

旋转

现在，我们只需要有效地实现伸展操作，就可完成所需的一切操作。

考虑怎么将某个节点高度提升一。我们称这个操作为旋转。

考虑怎么将 $2$ 提升到 $4$ 的位置。

那样，$4$ 该放到哪里？可以接到 $2$ 的右儿子上。$2$ 的右儿子放到哪里？放到 $4$ 的左儿子上，因为 $4$ 原来的左儿子是 $2$，现在已经空。其他子树不变。因此，变的只有 $2$ 和 $4$。

单旋与双旋

伸展操作能不能直接一直向上旋转呢？可以，但复杂度错误。

为了改善复杂度，我们需要引入双旋。

双旋是指，在伸展过程中，如果出现 $x$ 与 $x$ 的父亲同向，不能简单地旋转两次 $x$，而是要先旋转其父亲，再旋转 $x$。

我们如果想要将 $6$ 伸展到根，是不是需要双旋？答案是肯定的，因为 $4$ 和 $6$ 都是其父亲的右儿子，属于同向。如果是伸展 $3$，就不需要了。按照双旋的过程，我们先旋转 $4$，再旋转 $6$。也就是，先变成：

后旋转 $6$

光看上图，可能感觉双旋和单旋没有什么区别，但实际上在复杂度分析时，使用双旋可以保证某个性质，进而保证复杂度正确。

总之，我们已经知道了怎样以正确的复杂度将 $x$ 伸展到根。有关 Splay 的基本操作，就介绍完毕了。

附一份常数和美观程度都不错的实现。

复杂度

势能分析简介

我们发现，Splay 的复杂度来源于两部分，一部分是遍历，另一部分是伸展。让最终遍历到节点马上被伸展到根，就可以把复杂度都算在伸展里，进而只需证明伸展的复杂度。

我们采用势能分析。势能分析是指，引入某个势能函数 $\Phi(D)$，描述某时数据结构的状态。

设每次操作的代价是 $c_i$，每次操作后数据结构为 $D_i$。要证 $\sum c_i$ 有某上界。如果 $\Phi(D_n) - \Phi(D_0) = O(F(n))$，$\Phi(D_n) - \Phi (D_0) + \sum c_i = \sum (c_i + \phi(D_i) - \phi(D_{i - 1})) = O(G(n))$，显然 $\sum c_i = O(F(n) + G(n))$。

这样有什么好处？我们考虑，Splay 等数据结构复杂度分析的难处，在于我们只知道 $c_i$ 的一个很松的上界，而不好直接分析 $\sum c_i$。实际上，某个大的 $c_i$ 对数据结构的影响也是大的，会导致后续的操作 $c_i$ 更小；换句话说，不会出现所有 $c_i$ 都取到上界的情况。

引入势能函数后，每个很大的 $c_i$，可以用一个很小的 $\Phi(D_i) - \Phi(D_{i-1})$ 来平衡。因而可以更方便地放缩，并得到上界。

具体分析

我们设某个节点的势能函数为 $\phi(x) = \log \lvert x\rvert$（$\log$ 均以二为底；$\lvert x\rvert$ 表示 $x$ 的子树大小），$\Phi(D) = \sum \phi(x)$。显然的，$0\le \Phi(D) \lt n\log n$，并且 $\Phi(D_n) - \Phi(D_0) = O(n\log n)$。我们要证明每次伸展操作的均摊复杂度是对数。

伸展的分解

根据上面对 Splay 的介绍，我们可以将伸展分为三种具体操作。设 $x$ 为待伸展的节点，$y$ 为 $x$ 的父亲，$z$ 为 $y$ 的父亲。

• zig，即一次单旋，在 $y$ 为根时候发生。直接旋转 $x$，其深度减少一。发现这种旋转最多发生一次。

• zig-zig，即一次双旋，在 $y$ 和 $x$ 同向时发生。先旋转 $y$，后旋转 $x$。$x$ 深度减少二。

• zig-zag，即两次对 $x$ 的单选，在 $x$ 和 $y$ 不同向时发生。$x$ 深度减少二。

伸展的过程是数次 zig-zig 与 zig-zag 的组合，加上可能存在的一次 zig。

zig 的分析

旋转的复杂度为 $O(1)$，势能的变化量为

$\phi(x') + \phi(y') - \phi(x) - \phi(y) = \phi(y') - \phi(x) \le \phi(x') - \phi(x)$

因此摊还代价是 $O(1) + \phi (x') - \phi (x)$。

zig-zig 的分析

摊还代价是

$$ \begin{aligned} & c \ =& 1 + \phi(x') + \phi(y') + \phi(z') - \phi(x) - \phi(y) - \phi(z) \ =& 1 + \phi(y') + \phi(z') - \phi(x) - \phi(y) \ \end{aligned} $$

考虑怎么把 $1$ 去掉，因为如果引入 $1$，就会导致最终复杂度与旋转次数有关。

有：

$$ \begin{aligned} 2\phi(x') - \phi(x) - \phi(z') = \log (\dfrac{\lvert x'\rvert^2}{\lvert x\rvert\lvert z'\rvert}) \ge 1 \end{aligned} $$

这是因为 $\lvert x'\rvert \ge \lvert x\rvert+\lvert z'\rvert$。注意到不双旋时，此不等式不满足。这也是为什么双旋才能保证复杂度。

用这个不等式代换常数 $1$，得到

$$ \begin{aligned} & c \ \le& 2\phi(x') - \phi(x) - \phi(z') + \phi(y') + \phi(z') - \phi(x) - \phi(y) \ \le& 2\phi(x') - 2\phi(x) + \phi(y') - \phi(y) \ \le& 3\phi(x') - 3\phi(x) \ =& O(\phi(x') - \phi(x)) \end{aligned} $$

成功将常数消去，同时和前面的 $\phi(x') - \phi(x)$ 保持了一致。

zig-zag 的分析

类似的，我们有不等式：$2\phi(x') - \phi(y') - \phi(z') = \log (\dfrac{\lvert x'\rvert^2}{\lvert y'\rvert\lvert z'\rvert})\ge 1$

$$ \begin{aligned} & c \ &= 1 + \phi(x') + \phi(y') + \phi(z') - \phi(x) - \phi(y) - \phi(z) \ &= 1 + \phi(y') + \phi(z') - \phi(x) - \phi(y) \ &\le 2\phi(x') - \phi(y') - \phi(z') + \phi(y') + \phi(z') - \phi(x) - \phi(y) \ &\le 2\phi(x') - 2\phi(x) - \phi(y) \ &\le 2\phi(x') - 2\phi(x) \ &= O(\phi(x') - \phi(x)) \end{aligned} $$

综合

分析得到，zig 的摊还代价为 $O(1 + \phi(x') - \phi(x))$，而这种旋转最多一次；其他的两种旋转，摊还代价都是 $O(\phi(x') - \phi(x))$。这样，伸展的总代价就是 $O(\log \lvert x'\rvert - \log \lvert x\rvert + 1) = O(\log n)$。我们成功证明了伸展的复杂度是摊还对数，由此知道 Splay 的复杂度是正确的。