UPS

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

定义

基础定义

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

项：一个自然数与一个星号标记 ${\alpha }_i=(v_i,s_i)$ 。

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

正规化序列：一个序列 $S=[{\alpha }_0,{\alpha }_1,...,{\alpha }_{L-1}]$ 的正规化序列为 $\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}(S)=[\alpha {\text{'}}_0,\alpha {\text{'}}_1,...,\alpha {\text{'}}_{L-1}]$, 其中 $\alpha {\text{'}}_i=(v_i-v_0,s_i)$ 。

直接集与直接段

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

1. $i\in D(i)$;
2. 若 $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$ , 定义 $\mathrm{e}\mathrm{n}\mathrm{d}(i)=k_0$; 否则，定义 $\mathrm{e}\mathrm{n}\mathrm{d}(i)=M(i)$ 。

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

字典序比较与投影比较

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

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

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

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

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

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

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

父段与 Dropping 祖先段

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

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

若 $s_i=0$ , 通过以下流程计算出索引 $i$ 的 Dropping 祖先段：初始状态下定义 $c_0=i,r_0=i$ 。

循环进行以下步骤：

令 $p_n=\mathrm{p}\mathrm{s}(c_n)$ 。若 $p_n=-1$ ，则计算结束，得到 $\mathrm{d}\mathrm{r}\mathrm{o}\mathrm{p}(i)=r_n$ 。

否则，令 $\mathrm{R}=\mathrm{s}\mathrm{e}\mathrm{g}(\mathrm{r}{\phantom{A}}_n),\mathrm{P}=\mathrm{s}\mathrm{e}\mathrm{g}(\mathrm{p}{\phantom{A}}_n)$ 。

情况1： $\mathrm{R}<\mathrm{P}$

不更新状态，向上追溯父段：令 $\mathrm{c}{\phantom{A}}_{n+1}=\mathrm{p}{\phantom{A}}_n,\mathrm{r}{\phantom{A}}_{n+1}=\mathrm{r}{\phantom{A}}_n$ 。

情况2：$R\ge P$ 且 $R{<}_{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}P$

更新候选为当前段，并向上追溯父段：令 $\mathrm{c}{\phantom{A}}_{n+1}=\mathrm{p}{\phantom{A}}_n,\mathrm{r}{\phantom{A}}_{n+1}=\mathrm{p}{\phantom{A}}_n$ 。

情况3：$R\ge P$ 且 $R{\ge }_{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}P$

计算结束，得到 $\mathrm{d}\mathrm{r}\mathrm{o}\mathrm{p}(i)=r_n$ 。

坏根寻找

令 $d=\mathrm{d}\mathrm{r}\mathrm{o}\mathrm{p}(L-1)$。若 ${\mathrm{p}\mathrm{s}}^{m+1}(d)=-1$ , 则构建祖先段链 $[ps(d),p{s}^2(d),...,p{s}^m(d)]$。定义参考段 $R=[{\alpha }_d,{\alpha }_{d+1},...,{\alpha }_{L-1}]$ 。

按顺序枚举祖先段链。