[题解]GarsiaWachs算法

## [做法] GarsiaWachs算法 *更多内容及证明见后文 1. 找到满足 $q_{k-1} \lt q_{k+1}$ 的最小下标 $k$ 2. 找到满足 $q_{j-1} \gt q_{k-1} + q_k$ 的最大 $j \lt k$ 3. 从列表中清除 $q_{k-1}, q_k$ 4. 在 $q_{j-1}$ 之后插入 $q_{k-1} + q_k$ 5. $q_{-1}$ 和 $q_{n+1}$ 可以用 $\infty$ 处理 **例**：$q[5]=\{183,64,35,32,103\}$ | $q_{-1}$ | $q_0$ | $q_1$ | $q_2$ | $q_3$ | $q_4$ | $q_5$ | $k$ | $j$ | | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | | $\infty$ | 186 | 64 | 35 | 32 | 103 | $\infty$ | 3 | 1 | | $\infty$ | 186 | 67 | 64 | 103 | $\infty$ | | 2 | 1 | | $\infty$ | 186 | 131 | 103 | $\infty$ | | | 2 | -1 | | $\infty$ | 234 | 186 | $\infty$ | | | | 1 | -1 | | $\infty$ | 420 | $\infty$ | | | | | | | **代码实现：** 通过 $vector$ 模拟上述过程 **因为删除$erase$ 和 插入 $insert$ 操作速度较慢，代码需要O2优化** ~~我太菜了~~ ```cpp #include <bits/stdc++.h>//懒 using namespace std; int n, k, j; int ans, sum; vector<int> v; int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();} while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int main() { n = read(); v.push_back(INT_MAX - 1); for (int i = 1; i <= n; i++) v.push_back(read()); v.push_back(INT_MAX); while (n-- > 1) { for (k = 1; k <= n; k++) if (v[k - 1] < v[k + 1]) break; sum = v[k] + v[k - 1]; for (j = k - 1; j >= 0; j--) if (v[j] > v[k] + v[k - 1]) break; v.erase(v.begin() + k - 1); v.erase(v.begin() + k - 1); v.insert(v.begin() + j + 1, sum); ans += sum; } printf("%d", ans); return 0; } ``` ### 加西亚-瓦克斯(GarsiaWachs)算法. 这种算法是基于最优二叉树提出的，有一个概念叫做 **二叉树中预期比较次数**  根节点的 $level = 0$ 二叉查找树中给定几个概率值, $p_1, p_2,\ldots, p_n$ 和 $q_0, q_1, \ldots, q_n$ $p_i$ 表示查找参数是 $K_i$ 的概率， $q_i$ 表示查找参数介于 $p[K_i,K_i+1]$ 概率 查找预期比较次数是 ${\sum_{j=1}^n p_j(level+1)+{\sum_{k=0}^n}q_k(level_k)}$ $q_k$ 针对外节点的，其实这理解起来也不难，外节点是直接暴露在外面的 根据只要知道它的层数，比如 $1,2$ 两个外节点都在第 $3$ 层，这时候只要 $3 \times q_1$ 就可以知道 $1$ 出现的概率，也就可以知道比较次数了 $p_j$ 是针对内节点的，一定要通过外节点才能进入内节点，所以要$level + 1$ 上述公式叫 **树的成本**，预期比较次数为 外节点: $\{0,1,2,3\},2q_0+3q_1+3q_2+q_3$ 内节点: $\{1,2,3\},2p_1+3p_2+p_3$ 二者的和就是这个树的成本 **加西亚瓦克斯算法就是上述树的成本中，$p_k = 0$ 时候的特例** $$ c = \sum_{k=0}^nq_kl_k $$ #### 引理一，最优二叉树的转化 如果 $q_{k-1} \gt q_{k+1}$，则在每棵最优树中，$l_k \le l_{k+1}$ 如果 $q_{k-1} = q_{k+1}$，则在某些最优树中，$l_k \le l_k+1$ 证明方法，看一个二叉树的剪裁  不妨设 $q_{k-1} \ge q_{k+1}$，并且考虑$l_k \gt l_{k+1}$ 那么树的形状一定如上图所示，$k$ 为右孩子 这个时候如果按照图中的方式剪裁，两条线中的部分裁掉 让左子节点 $L$ 成为新的 $parent$ ，并且 $[l_k-1,l_{k+1}]$ 部分裁掉 使得 $k$ 节点上浮，并且 $k+1$ 节点下沉一个单位 不妨设 $L$ 是一个权值为 $w$ 的子树， $w \ge q_{k-1}$ ，这是显然的 因为我们假定 $q_{k-1} \ge q_{k+1}$ ，那么在左边的外节点权值更大 这样裁剪之后，总的权值变化包括 $3$ 个部分 1） $L$ 裁掉，$-w $} 2） $k$ 上浮，$-q_k(l_k-l_{k+1}-1)$ 3） $k+1$下沉，$q_{k+1}$ $$\Delta = -w-q_k(l_k-l_{k+1}-1)+q_{k+1} \le -q_{k-1}-q_k(l_k-l_{k-1}-1)+q_{k+1}\le q_{k+1} - q{k-1}$$ 如果 $q_{k+1}-q_{k-1}\lt0$ ，显然不是最优的，矛盾 另外，如果 $q_{k-1}=q_{k+1}$ ，则已经将一棵最优树转变成为另一颗了 $k-1$ 和 $k+1$ 这个层次上等价，$l_{k-1}=l_{k+1}$，构成最优树 #### 引理二，树的旋转调整分支高度 假定 $j$ 和 $k$ 是满足 $j \lt k$ 的下标，并且满足 1. 对于 $1\le i\lt k,q_{i-1} \gt q_{i+1}$ 2. $q_{k-1} \le q_{k+1}$ 3. 对于 $j \le i \lt k-1,q_i \lt q_{k-1} + q_k$ 4. $q_{j-1} \ge q_{k-1} + q_k$ 于是，**存在一颗满足 $l_{k-1}=l_k$ 的最优树**，同时，它还满足以下条件之一 $a. l_j=l_k-1$ $b.l_j=l_k$ 且 $j$ 为左孩子 证明方法，从引理一直到 $q_{k-1} \le q_{k+1}$，存在满足 $l_{k-1}\ge l_k$ 的最优树 对于 $1 \le i \lt k$ 而言，还有 $l_1 \le l_2 \le \ldots \le l_k$，因此有 $l_{k-1}=l_k$ 其次，我们关注树的层次，如下图所示  先看如图所示的三层结构，对于满足 $j \le s \lt k-1 $ 的 $s$ 有 $l_s \lt l_k-1 \le l_{s+1}$，假设 $t$ 是满足 $l_t=l_k$ 且小于 $k$ 的最小下标 于是，对于 $s\lt i\lt t $ ，有 $l_i = l_k-1$ 并且 $s+1$ 为左孩子，或者 $s+1=t$，这样我们可以通过二叉树旋转等操作 **让部分节点上升，部分节点下降** 如果让s所在的分支下降，t所在的分支上升的话 $\Delta=q_s-q_t-q_t+1$，因为$t \lt k$，所以 $q_t\gt q_{k-1} \& q_{t+1} \gt q_k$ $\Delta=q_s-q_t-q_{t+1} \le q_s-q_{k-1}-q_k$ 如果 $q_s\lt q_{k-1}+q_k$ ，所以 $\Delta \lt 0$ ，次时能得到更优的二叉树 旋转之后， $l_j \ge l_k-1$ 再看最后一个部分，如果 $l_j=l_k$ 并且 $j$ 是有孩子的话，则一定有如下情况  如果旋转二叉树，让 $j-1$ 下降，让 $k-1,k$ 这个分支上升 $\Delta = -q_{j-1}+q_{k-1}+q_k \le 0$ ，此时二叉树并不是最优的，和假设矛盾 #### 引理三，加西亚瓦克斯算法核心 如上所述，可以考虑删除 $q_{k-1}$ 和 $q_k$ 并且在 $q_{j-1}$ 之后插入 $q_{k-1}+q_k$ 所得到的概率 $(q_0',\ldots ,q_{n-1}')=(q_0,\ldots,q_{j-1}, q_{k-1}+q_k,q_j,\ldots,q_{k-2},q_k+1,\ldots,q_n)$ 于是，$C(q_0',\ldots,q_{n-1}')\le C(q_0,\ldots,q_n)-(q_{k-1}+q_k)$ 排列方式 $0,\ldots,j-1,k-1,k,j,\ldots,k-2,k+1,\ldots,n$ 更优 这就很简单了，根据**引理二**，如果是$b$类型的，只需要重命名这些叶节点就可以 如果是$a$类型的呢？可以通过**旋转二叉树**的方式，**让 $(k-1,k)$ 这两个叶子对** **上升一个高度**，实际上就是在 $l_k$ 这个高度上，减掉 $q_{k-1}+q_k$ ，然后向左移动 在 $j-1$ 后面插入即可 #### 引理四 任何一个排列方式如**引理三**所述的树，都可以转化成为 成本相同，叶子排列顺序为 $0,1,\ldots,n$ 的树 1. 如果 $j=k-1$ ，显然成立 2. 如果不相等，因为 $q_{j-1} \ge q_{k-1} + q_k \gt q_j$ (**引理二**条件) $0,\ldots,j-1,k-1,k,j,\ldots,k-2,k+1,\ldots,n$ ↑ ↑ j k - 1 $q'$ 的下标表示如上所示，所以对于 $j \le i \le k-1$，有 $q_{i-1}' \gt q_{i+1}'$ 于是根据引理，有 $l_x \le l_j \le \ldots \le l_{k-2}$，其中 $l_x$ 是 $x$ 的级别，并且 对于 $j \le i \lt k-1$，$l_i$ 是 $i$ 的级别 $a.$ 如果 $l_x=l_{x-2}$，都在同一级上 ​ $i,\ldots,k-2,x$ 替换序列 $x,i,\ldots,k-2$ $b.$ 否则，假定 $l_s=l_x$，$l_{s+1}>l_x$，令 $l=l_x+1$，并且 ​ $l$ 是节点 $(k-1,k)$ 的公共级别，使得 ​ $l \le l_{s+1}\le \ldots\le l_{k-2}$，最后可以通过循环位移操作，使得 ​ $k-1,k,s+1,\ldots,k+2$ 变成 $s+1,\ldots,k-2,k-1,k$ ~~有看不懂的别找我~~ ~~这个 $\LaTeX$ 快敲死我了~~ 终