UPS：修订间差异

←上一编辑下一编辑→

可视化wikitext

2026年7月8日 (三) 09:48的版本

UPS（Upper Projection Sequence, 向上投影序列）是由 Optimism 最初创作，Alice 完善的记号，旨在以序列形式模拟向上投影。

定义

基础定义

一个 UPS 表达式由一组有序排列的项组成。

项：一个自然数与一个星号标记 $α_{i} = (v_{i}, s_{i})$ 。

父项：一个索引的父项 $p (i)$ 为最大的 $j < i$ , 满足 $v_{j} < v_{i}$ 。若不存在满足条件的项，则记作 $p (i) = - 1$ 。

正规化序列：一个序列 $S = [α_{0}, α_{1}, . . ., α_{L - 1}]$ 的正规化序列为 $n o r m (S) = [α'_{0}, α'_{1}, . . ., α'_{L - 1}]$ , 其中 $α'_{i} = (v_{i} - v_{0}, s_{i})$ 。

直接集与直接段

一个索引 $i$ 的直接集定义为：

$i \in D (i)$ ;
若 $p (j) \in D (i), s_{p (j)} = 1$ , 则 $j \in D (i)$ 。

定义直接段结尾：令 $M (i) = \max (t | t \in D (i))$ 。若存在 $k$ 使得 $v_{k} = \min (v_{j} | j > M (i), p (j) \in D (i))$ , 找到其中索引最小的 $k_{0}$ , 定义 $e d (i) = k_{0}$ ; 否则，定义 $e d (i) = M (i)$ 。

定义索引 $i$ 的直接段为 $s e g (i) = [α_{i}, . . ., α_{e d (i)}]$ 。

字典序比较与投影比较

在进行字典序比较与投影比较之前，首先要将待比较序列的 $α_{L - 1}$ 替换为 $α *_{L - 1} = (v_{L - 1}, 1)$ ，并进行正规化。

字典序比较记为 $S < T$ , 为逐项首先比较数值（数值大者更大），其次比较星号（有星号者更大）。若前缀完全相同，则更长者更大。

投影比较记为 $S <_{p r o j} T$ , 比较流程如下：

首先定义 $S = [α_{0}, α_{1}, . . ., α_{L - 1}]$ 的投影深度 $d e p (S) = v_{L - 1}$ 。若 $d e p (S) < d e p (T)$ , 则 $S <_{p r o j} T$ 。

若 $d e p (S) = d e p (T) = 0$ , 则 $S =_{p r o j} T$ 。

若 $t = p (L - 1) \geq 0$ , 则定义 $S$ 的投影子序列为 $p r o j (S) = n o r m ([α'_{t}, α_{t + 1}, . . ., α_{L - 1}])$ , 其中 $α'_{t} = (v_{t}, 0)$ 。若 $t = - 1$ , 定义 $S$ 的投影子序列为空序列。

若 $d e p (S) = d e p (T)$ 且 $p r o j (S) < p r o j (T)$ , 则 $S <_{p r o j} T$ 。若 $d e p (S) = d e p (T)$ 且 $p r o j (S) = p r o j (T)$ , 则 $S =_{p r o j} T$ 。

父段与 Dropping 祖先段

定义索引 $i$ 的父段起始索引为： $p s (i) = {\begin{cases} - 1, & p (i) = - 1; \\ p (i), & s_{p (i)} = 0; \\ p s (p (i)), & s_{p (i)} = 1 . \end{cases}$ 。

定义索引 $i$ 的父段为 $s e g (p s (i))$ 。

若 $s_{i} = 0$ , 通过以下流程计算出索引 $i$ 的 Dropping 祖先段：

@@ 第8行： / 第8行： @@
 项：一个自然数与一个星号标记 <math>\alpha_i = (v_i, s_i)</math> 。
-父项：一个索引的父项 <math>p(i)</math> 为最大的 <math>j < i</math>, 满足 <math>v_j < v_i</math> 。
+父项：一个索引的父项 <math>p(i)</math> 为最大的 <math>j < i</math>, 满足 <math>v_j < v_i</math> 。若不存在满足条件的项，则记作 <math>p(i) = -1</math> 。
 正规化序列：一个序列 <math>S = [\alpha_0, \alpha_1, ..., \alpha_{L-1}]</math> 的正规化序列为 <math>\mathrm{norm}(S) = [\alpha'_0, \alpha'_1, ..., \alpha'_{L-1}]</math>, 其中 <math>\alpha'_i = (v_i - v_0, s_i)</math> 。
@@ 第28行： / 第28行： @@
 投影比较记为 <math>S <_\mathrm{proj} T</math>, 比较流程如下：
-首先定义 <math>S = [\alpha_0, \alpha_1, ..., \alpha_{L-1}]</math>的投影深度 <math>\mathrm{dep}(S) = v_{L-1}</math> 。若<math>\mathrm{dep}(S) < \mathrm{dep}(T)</math> , 则 <math>S <_\mathrm{proj} T</math> 。
+首先定义 <math>S = [\alpha_0, \alpha_1, ..., \alpha_{L-1}]</math>的投影深度 <math>\mathrm{dep}(S) = v_{L-1}</math> 。若 <math>\mathrm{dep}(S) < \mathrm{dep}(T)</math> , 则 <math>S <_\mathrm{proj} T</math> 。
 若 <math>\mathrm{dep}(S) = \mathrm{dep}(T) = 0</math> , 则<math>S =_\mathrm{proj} T</math> 。
-令 <math>t = p(L-1)</math> , 则定义 <math>S</math> 的投影子序列为 <math>\mathrm{proj}(S) = \mathrm{norm}([\alpha'_{t}, \alpha_{t+1}, ..., \alpha_{L-1}])</math> , 其中 <math>\alpha'_t = (v_t, 0)</math> 。
+若 <math>t = p(L-1) \ge 0</math> , 则定义 <math>S</math> 的投影子序列为 <math>\mathrm{proj}(S) = \mathrm{norm}([\alpha'_{t}, \alpha_{t+1}, ..., \alpha_{L-1}])</math> , 其中 <math>\alpha'_t = (v_t, 0)</math> 。若 <math>t = -1</math> , 定义 <math>S</math> 的投影子序列为空序列。
 若 <math>\mathrm{dep}(S) = \mathrm{dep}(T)</math> 且 <math>\mathrm{proj}(S) < \mathrm{proj}(T)</math> , 则 <math>S <_\mathrm{proj} T</math> 。若 <math>\mathrm{dep}(S) = \mathrm{dep}(T)</math> 且 <math>\mathrm{proj}(S) = \mathrm{proj}(T)</math> , 则 <math>S =_\mathrm{proj} T</math> 。
+=== 父段与 Dropping 祖先段 ===
+定义索引 <math>i</math> 的父段起始索引为：<math>\mathrm{ps}(i) = \begin{cases}-1 ,&p(i) = -1;\\ p(i),&s_{p(i)} = 0;\\ \mathrm{ps}(p(i)),&s_{p(i)} = 1.\end{cases}</math> 。
+定义索引 <math>i</math> 的父段为 <math>\mathrm{seg}(\mathrm{ps}(i))</math> 。
+若 <math>s_i = 0</math> , 通过以下流程计算出索引 <math>i</math> 的 Dropping 祖先段：