RSK 词插入与逆恢复

插入表保留一份经过有序整理的值，但整理会抹去部分原位置。记录表专门记住每次整理最后在哪个角格结束。逆过程先由最大时刻找到最后的新格，再沿行反向取回被撞出的值，两张表合起来才恢复原词。

这不是把词简单排序。每次较小字母进入上行，都会把某个较大的字母推到下行；下行仍需继续整理。形成的形状记录了原来的先后关系，下面的第一行不变量会把它与最长弱递增子序列连接起来。

七个字母的完整轨迹 ​

输入$w=1323213$。按每次插入后的行列出$P$，并记录新增格：

第六步最能看出严格比较：新1越过第一行已有的1，替换第二列的2；这个2替换第二行第一列的3；最后3进入第三行。最终

形状为$(4,2,1)$，内容为$(2,2,3)$。第一行长4；原词的第$1,3,5,7$个位置给出弱递增子序列$1,2,2,3$，确实达到这个长度。

图保留本例第六步前后的实际状态。红框标出将被替换的旧值，绿框标出更新位置；Q中的6单独确定逆过程应从哪里开始。

只有P或只有形状都不足以恢复 ​

词$132$和$312$都得到

但记录表分别是第一行$(1,2)$、第二行$(3)$，以及第一行$(1,3)$、第二行$(2)$。所以$P$独自没有编码整个词，形状更没有。式(1)的逆输入必须包含完整的两张表。

若把“第一个严格大于”改成“第一个大于等于”，词$11$会被放成竖列$1,1$，直接违反本页列严格条件；它的最长弱递增长度明明是2，错误变体的第一行却只有1。其他插入约定可以研究不同对象，但不能沿用式(1)的输出合同。

第一行的值也不一定按原词顺序组成一份子序列。主例最终第一行为$1,1,2,3$，原词中的第二个1已在第6位，后面没有2，因此这个四元组本身不是原词子序列。它保存的是不同长度子序列各自的最小结尾值，不是一条共同的最优路径。若需要实际下标见证，应另外记录前驱。

插入为何保持半标准形状 ​

在某行把$x$放进第一个旧值$y>x$的位置，左边所有值都不大于$x$，右边所有值都不小于旧$y$，故行弱增保留。若没有这种$y$，追加同样保留行弱增。

再看相邻两行。设上一行在第$c$列撞出$y$，将它送入下一行。若下一行原来有第$c$格，列严格保证该旧值大于$y$，所以它的首个大于$y$的位置不会在$c$右侧；若下一行较短，追加位置也不超过$c$。因此撞击位置向下走时弱向左，被撞出的值则严格增加。

假设下一行将$y$放在第$d\le c$列。若$d=c$，上方已经换成一个严格小于$y$的值；若$d<c$，上方第$d$格还位于上一步替换位置左边，其值不大于上一步的新值，也严格小于$y$。所以新值与上方仍严格有序。它与下方原值的关系也安全，因为新值小于被替换的旧值；若随后下方同列被更新，送下去的又是严格更大的旧值。

最终追加位置不超过上一行撞击列，所以上一行足够长；下一行原来不会比当前行更长，因此新格也没有下邻。这恰是一个合法外角。每次处理只向下一行推进，有限表不可能无限撞击，故必然结束。

于是$P$一直半标准，且形状每次合法增加一格。$Q$给新格填一个比已有标签都大的时刻；新格没有右邻或下邻，故行列严格条件保留，$Q$一直标准。

从最大时刻开始逆插 ​

给定任意合法同形表对$(P,Q)$，令$k=N,N-1,\dots ,1$：

1. 在$Q$中找到标签$k$，删去它所在格；标准性保证它是可删角格。
2. 从$P$同一格取出值$x$并删格。若它在第一行，直接把$x$作为$w_k$。
3. 否则走到上一行，找其中最右一个严格小于$x$的值$y$，把该处换成$x$，再以$y$作为新的$x$继续向上一行。越出第一行时输出$w_k=x$。

删格后保留空形边界；最下行若为空，就从行长表中去掉。按照倒序得到的$w_N,\dots ,w_1$最后反向排列，就是原词。

“最右严格小于”的位置总存在。第一步时，所删格的上方存在且值严格更小；之后，刚被取出的旧值在更上一行原本也有一个严格更小的上邻。逆撞位置逐层弱向右，因为这个上邻已经提供一个候选列。

替换同样保持行弱增：所选位置左侧值不大于旧$y$，右侧值都不小于新$x$。与更上方比较，旧上邻小于$y<x$。与下方比较，若那里有格，下方刚在一个不更靠右的列放入了比当前$x$更大的值，行弱增使下方该列的值也严格更大；初次删外角时，这些右侧下邻本就不存在。因此每一步逆撞都留下合法的半标准表。

两个严格比较怎样保证互逆 ​

一次正插在第$c$列以$x$替换$y>x$后，右侧元素仍都不小于$y$，第$c$列却已经严格小于$y$。因此逆插携带$y$返回这一行时，“最右小于$y$”恰好选回$c$，取回$x$并放回$y$。

反过来，逆插在某行选择最右$y<x$的位置$c$，放入$x$。该位置左边都不大于$y$，新位置值$x$严格大于$y$，所以再正插$y$时，“第一个大于$y$”恰选$c$并撞出$x$。每一行局部互逆，整条撞击路径就互逆。$Q$又准确选定最后的新角格，逐时刻归纳便证明双射式(1)。

正插每次只是移动旧值并加一个新字母，故$P$内容等于输入词内容。这也保证逆插不会凭空产生新符号。输入若形状不同、Q缺标签或行列约定不符，应先拒绝，不能把逆过程中“找不到位置”当成一份合法编码。

对式(2)，先删除Q中的7，取出3；再删除6，从第三行取出3，在第二行最右小于3的位置取出2，再在第一行最右小于2的位置取出1。因此最后两字依次恢复为3、1。继续得到逆序输出$3,1,2,3,2,3,1$，反转即$1323213$。

第一行为何给最长弱递增长度 ​

处理词的某个前缀后，设第一行为$a_1\le \cdots \le a_L$。更强的不变量是：$a_j$等于该前缀中所有长度$j$弱递增子序列的最小末值；超过$L$的长度没有这种子序列。空前缀时成立。

读入$x$，第一行选择$c=1+\mathrm{\#}\{j:a_j\le x\}$。若$c>1$，原有长度$c-1$的子序列末值$a_{c-1}\le x$，接上当前位置即得到长度$c$、末值$x$；$c=1$时直接取新单字。若$c\le L$，原$a_c>x$，所以$x$改进长度$c$的最小末值；若$c=L+1$，它创造一个新长度。

对$j<c$，旧$a_j\le x$，新字不能给更小末值。对$j>c$，若要用新$x$结束长度$j$的子序列，就需此前存在长度$j-1$且末值不超过$x$的子序列；其最小末值至少为$a_c>x$，不可能。因此只有第$c$项需要更新，恰是首行插入规则。归纳完成证明。

这里讨论弱递增，等号允许；它与严格递增子序列的长度可能不同。正文并未由首行证明推导所有行的Greene不变量，也未借此无证明地承诺最长递减长度接口。

双射把表权和变成词计数 ​

取$A=[m]$。指定形状$\lambda$后，P与Q可以独立选，逆算法始终恢复唯一词，所以

实际调用钩长与钩内容公式理路钩长与有限字母计数Hook-length formula · Hook-content formula · Young tableau hook formulas · 钩长公式 · 钩内容公式从表权行列式推出标准表钩长积与有限字母半标准表钩内容积，证明行钩缺项恒等式并处理重合变量、空形和斜形边界。，$\lambda =(4,2,1)$、$m=3$给$35\cdot 15=525$。进一步用表权系数理路Jacobi–Trudi 与表格权计数Jacobi-Trudi identity · Jacobi–Trudi formula · Tableau expansion of Schur polynomials将既有Schur交错商连接完全齐次行列式和半标准表权和，完整证明系数分解、首次相交换尾及列严格对应。，若$K_{\lambda ,a}$为指定内容$a$的P表数，则

主形状的内容$(3,2,2)$有两张P，因此有70份词；所有这个内容的词共有$7!/(3!2!2!)=210$份，其余词属于其他形状。对全部形状相加，又得到$m^N=\sum _{\lambda ⊢N}{g}_{\lambda }(m)f^{\lambda }$。当输入是$[N]$的排列，P也标准，便得$N!=\sum _{\lambda ⊢N}(f^{\lambda }{)}^2$。空词的两条总和都按唯一空对象取1。

直接实现的成本 ​

朴素实现逐行线性寻找替换位置。一次插入或删除至多扫描当时表中的全部格子，再做常数次行操作；$N$次总比较成本为$O((N+1{)}^2)$，两张表及恢复词占$O(N+1)$个槽。这里把一次符号比较计为一步；大整数、长字符串的比较成本另计。

附件的insert默认不保存历史，符合上述核心空间界；若打开record_trace，另外保留每步完整P快照和撞击记录，累计需要$O((N+1{)}^2)$个槽。终点为了展示七步证书显式打开这一选项，批量纤维核验则关闭。输出完整轨迹比只输出最终表对承担更多存储责任。

若只需最长弱递增长度，可仅保存第一行并用二分寻找首个大于$x$的位置，得到$O(N\log (N+1))$次比较和$O(N+1)$槽，但这不会输出完整P、Q或保证能逆恢复原词。缩减输出责任之后，才能删去其余状态。