UPS

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 祖先段：