查看“︁UPS”︁的源代码

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

其极限表达式为 <math>0, 1, 2*, 3*, 4*, ...</math> 。

== 定义 ==

=== 基础定义 ===
一个 UPS 表达式由一组有序排列的项组成。

项：一个自然数与一个星号标记 <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) = -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> 。

=== 直接集与直接段 ===
一个索引 <math>i</math> 的直接集定义为：

# <math>i \in D(i)</math>;
# 若 <math>p(j) \in D(i), s_{p(j)} = 1</math>, 则 <math>j \in D(i)</math> 。
定义直接段结尾：令 <math>M(i) = \max(t | t \in D(i))</math> 。若存在 <math>k</math> 使得 <math>k > M(i), p(k) \in D(i)</math> 且 <math>v_k = \min (v_j | j > M(i), p(j) \in D(i))</math> , 找到其中索引最小的 <math>k_0</math> , 定义 <math>\mathrm{end}(i) = k_0</math> ; 否则，定义 <math>\mathrm{end}(i) = M(i)</math> 。

定义索引 <math>i</math> 的直接段为 <math>\mathrm{seg}(i) = [\alpha_i, \alpha_{i+1}, ..., \alpha_{\mathrm{end}(i)}]</math> 。

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

字典序比较记为 <math>S < 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) \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 祖先段：初始状态下定义 <math>c_0 = i, r_0 = i</math> 。

循环进行以下步骤：

令 <math>p_n = \mathrm{ps}(c_n)</math> 。若 <math>p_n = -1</math> ，则计算结束，得到 <math>\mathrm{drop}(i) = r_n</math> 。

否则，令 <chem>R = \mathrm{seg}(r_n), P = \mathrm{seg}(p_n)</chem> 。

情况1： <chem>R < P</chem>

不更新状态，向上追溯父段：令 <chem>c_{n+1} = p_n, r_{n+1} = r_n</chem> 。

情况2：<math>R \ge P</math> 且 <math>R <_\mathrm{proj} P</math>

更新候选为当前段，并向上追溯父段：令 <chem>c_{n+1} = p_n, r_{n+1} = p_n</chem> 。

情况3：<math>R \ge P</math> 且 <math>R \ge_\mathrm{proj} P</math>

计算结束，得到 <math>\mathrm{drop}(i) = r_n</math> 。

=== 坏根寻找 ===
若 <math>s_{L-1} = 1</math> , 以此流程确定坏根。

令 <math>l > 0</math> 为最小的自然数使得 <math>s_{p^l(L-1)} = 0</math> 。定义 <math>a = p^l(L-1), d = \mathrm{drop}(a)</math> 。若 <math>\mathrm{ps}^{m+1}(a) = -1</math> , 则构建祖先段链 <math>A = [\mathrm{ps}(a), \mathrm{ps}^2(a), ..., \mathrm{ps}^m(a)]</math>。定义参考段 <math>R = [\alpha_d, \alpha_{d+1}, ..., \alpha_{L-1}]</math> 。若 <math>d = \mathrm{ps}^k(a)</math> , 则将 <math>\mathrm{ps}(a)</math> 到 <math>\mathrm{ps}^k(a)</math> 预先标记为跳过。

按顺序枚举祖先段链。

对于当前枚举到的 <math>a_j \in A</math> , 若其被标记为跳过，则跳过本项。否则令 <math>d_j = \mathrm{drop}(a_j)</math> , 并构造子序列 <math>T_j = [\alpha_{d_j}, \alpha_{d_j+1}, ..., \alpha_{\mathrm{end}(a_j)}]</math> 。令 <math>\mathrm{ps}^s(a) = a_j, \mathrm{ps}^e(a) = d_j</math>  , 定义 <math>C = [\mathrm{ps}^s(a), \mathrm{ps}^{s+1}(a), ..., \mathrm{ps}^e(a)]</math> 。

情况1：<math>R < T_j</math>

将 <math>C</math> 中所有索引标记为跳过，并继续枚举。

情况2：<math>R \ge T_j</math>

找到最大的 <math>q \in C</math> 使得 <math>\mathrm{seg}(q) < \mathrm{seg}(a)</math> , 计算结束，坏根 <math>\rho = \mathrm{end}(q)</math> 。

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

=== 展开 ===
定义  <chem>S' = [\alpha_0, \alpha_1, ..., \alpha_{L-2}]</chem> 。

若 <math>v_{L-1} = 0</math> , 则展开结果为 <math>S'</math> 。

若 <math>s_{L-1} = 0</math> , 定义坏根 <math>\rho = p(L-1)</math> 。若 <math>s_{L-1} = 1</math> , 按上述流程确定坏根。

定义阶差 <math>\delta = \begin{cases}0 ,&s_{L-1} = 0;\\ v_{L-1} - v_\rho,&s_{L-1} = 1.\end{cases}</math> , 追加块 <math>B^{+k} = [\alpha^{+k}_\rho, \alpha^{+k}_{\rho+1}, ..., \alpha^{+k}_{L-2}]</math> , 其中 <math>\alpha^{+k}_i = (v_i + k \cdot \delta, s_i)</math> 。

展开结果的基本列第 <math>m</math> 项为 <chem>S' + B^{+1} + B^{+2} + ... + B^{+m}</chem> , 其中 <math>+</math> 为序列拼接。

若表达式无坏根或坏根为 <math>-1</math> , 则该表达式无法展开。

== 展开器 ==
[https://smilelee-lyx.github.io/ne-rewritten/ NE Rewritten] 上可进行 UPS 的展开。