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$ 。

坏根寻找

若 $s_{L-1}=1$ , 以此流程确定坏根。

令 $d=\mathrm{d}\mathrm{r}\mathrm{o}\mathrm{p}(L-1)$。若 ${\mathrm{p}\mathrm{s}}^{m+1}(L-1)=-1$ , 则构建祖先段链 $A=[\mathrm{p}\mathrm{s}(L-1),{\mathrm{p}\mathrm{s}}^2(L-1),...,{\mathrm{p}\mathrm{s}}^m(L-1)]$。定义参考段 $R=[{\alpha }_d,{\alpha }_{d+1},...,{\alpha }_{L-1}]$ 。若 $d={\mathrm{p}\mathrm{s}}^k(L-1)$ , 则将 $\mathrm{p}\mathrm{s}(L-1)$ 到 ${\mathrm{p}\mathrm{s}}^k(L-1)$ 预先标记为跳过。

按顺序枚举祖先段链。

对于当前枚举到的 $a_j\in A$, 若其被标记为跳过，则跳过本项。否则令 $d_j=\mathrm{d}\mathrm{r}\mathrm{o}\mathrm{p}(a_j)$ , 并构造子序列 $T_j=[{\alpha }_{d_j},{\alpha }_{d_j+1},...,{\alpha }_{\mathrm{e}\mathrm{n}\mathrm{d}(a_j)}]$ 。令 ${\mathrm{p}\mathrm{s}}^s(L-1)=a_j,{\mathrm{p}\mathrm{s}}^e(L-1)=d_j$ , 定义 $C=[{\mathrm{p}\mathrm{s}}^s(L-1),{\mathrm{p}\mathrm{s}}^{s+1}(L-1),...,{\mathrm{p}\mathrm{s}}^e(L-1)]$ 。

情况1：$T_j\ge R$

找到最大的 $q\in C$ 使得 $\mathrm{s}\mathrm{e}\mathrm{g}(q)<\mathrm{s}\mathrm{e}\mathrm{g}(\mathrm{p}\mathrm{s}(L-1))$ , 计算结束，坏根 $\rho =\mathrm{e}\mathrm{n}\mathrm{d}(q)$ 。

情况2：$T_j>R$

将 $C$ 中所有索引标记为跳过，并继续枚举。

若 $A$ 中索引已耗尽而仍未得到坏根，则该表达式无坏根。

展开

若 $v_{L-1}=0$ , 则展开结果 $\mathrm{S}{\phantom{A}}^{\prime }=[\mathrm{\alpha }{\phantom{A}}_0,\mathrm{\alpha }{\phantom{A}}_1,\dots ,\mathrm{\alpha }{\phantom{A}}_{\mathrm{L}-2}]$。

若 $s_{L-1}=0$ , 定义坏根 $\rho =p(L-1)$ 。