定义
设 \(x=(x_1,\dots,x_m)\) 是 \(n\) 的一个划分。\(x_1\ge x_2\ge\cdots\ge x_m\)。
定义 1（杨图）：一个 \(m\) 行的表格，第 \(i\) 行有 \(x_i\) 列（左对齐）。
定义 2（杨表）：将 \(1\sim n\) 填入杨图，满足每一行和每一列严格递增。
定义 3（半杨表）：将 \(n\) 个正整数填入杨图，满足每一行不严格递增，每一列严格递增。
定义 4（行插入）：设当前有一个杨表，一个行插入操作有一个参数 \(x\)。找到第一行第一个 \(>x\) 的数 \(x'\)，用 \(x\) 替换 \(x'\)；然后找到第二行第一个 \(>x'\) 的数 \(x''\)，用 \(x'\) 替换 \(x''\) …… 循环往复，直到把一个数插入新的一行（空行）或者这一行不存在更大的数（放在末尾）。
容易发现杨表插入后还是杨表。
定义 5（列插入）：与行插入类似。
定义 6（行删除）：可以看作是行插入的还原操作。取最后一行的数 \(x\)，找到上一行最后一个 \(<x\) 的数 \(x'\) ……
定义 7（列删除）：与行删除类似。
定义 8（勾长）：记 \(h(i)\) 为格子 \(i\) 的勾长。\(h(i)=\) \(i\) 下方格子数 + 右方格子数 + 1。
RSK Correspondence
设当前有一个排列 \(\pi=(\pi_1,\dots,\pi_n)\)，按顺序把 \(\pi\) 行插入一个初始为空的杨表。得到的杨表记作 \(P_{\pi}\)。
另外构造一个杨表 \(Q_{\pi}\)，在 \(\pi_i\) 插入时新增的格子里填 \(i\)。
把 \(P_{\pi}\) 叫做正表，\(Q_{\pi}\) 叫做副表。容易发现 \(P_{\pi},Q_{\pi}\) 是形态相同的杨表。
定理：排列 \(\pi\) 与杨表对 \((P_{\pi},Q_{\pi})\) 构成一一对应。
证明：因为有删除操作，从 \(\pi\) 构建 \(P_{\pi},Q_{\pi}\) 的过程是可逆的。
推论：\(n!=\sum_{x}c(x)^2\)，\(x\) 为 \(n\) 的一个划分（对应了一个杨图的形态），\(c(x)\) 为形态为 \(x\) 的杨表个数。
证明：排列与杨表对一一对应，枚举杨图然后枚举 \(P,Q\) 的填法。
Hook Formula：假设有一个杨图 \(x\)，\(c(x)=\dfrac{n!}{\prod_i h(i)}\)，\(i\) 是 \(x\) 里的格子。
定理：不严格递增的坐标序列与半杨表对一一对应。
（这里比较坐标的大小是按字典序比较）
证明：设坐标序列为 \((u_1,v_1),(u_2,v_2),\dots,(u_k,v_k)\)，把 \(v_1\sim v_k\) 插入一个表，得到半杨表 \(P_x\)；\(Q_x\) 定义为在每次新增加的格子里填 \(u_i\)。
性质
性质 1：若 \(\pi\) 对应 \((P_{\pi},Q_{\pi})\)，则 \(\pi^{-1}\) 对应 \((Q_{\pi},P_{\pi})\)。（拓展：如果一个递增坐标序列 \(x\) 对应半杨表对 \((P_x,Q_x)\)，交换 \(x_i\) 的两维后对应半杨表对 \((Q_x,P_x)\)）
证明：直接证明拓展版本，也就是普通序列和半杨表。这显然拓展版本强于原命题。
先来几个定义。
考虑一个不严格递增坐标序列 \(x\) 对应到一个 \(2\times n\) 的矩阵 \(A\)：\(A[1][i]=x_i\) 的第一维，\(A[2][i]=x_i\) 的第二维。
同时考虑一个不严格递增坐标序列 \(x\) 对应到一个 \(V\times V\) 的方阵 \(M\)：\(M[i][j]=\) 两维分别等于 \(i,j\) 的 \(x_k\) 个数。
显然序列、矩阵、方阵是一一对应的。
如果 \(x\) 对应方阵 \(M\)，定义 \(P_M=P_x\)。
开始正式证明。
观察到若 \(x\) 对应了 \(A\)，则 \(x^{-1}\) 对应 \(A^{T}\)。
因此可以转化命题为：\(P_{M^T}=Q_M,Q_{M^T}=P_M\)。
简单起见，假设没有重复元素（坐标互不相等），此时 \(A\) 是 \(0/1\) 方阵。
考虑 \(P_A,Q_A\) 的第一行。玩一个例子：\((1,3)(1,4)(2,3)(3,1)(3,4)(4,2)\)。
发现每一列上曾经存在过的数，构成一个递减序列。进一步观察，每一列都是从剩下没选的元素里贪心取 LDS 的结果，也就是贪心地把序列划分成若干个下降序列。
在方阵里看，这样的划分实际上是从一个 \(1\) 出发，向右上方贪心找链。定义极值点为方阵里左上方没有 \(1\) 的点，那么第一条链是所有极值点、第二条链是剩下点里的极值点 ……
观察到 \(P_M\) 的第一行（设 \(t\) 列）就是每条链的链尾列号。而 \(Q_M\) 的第一行呢？显然也是 \(t\) 列，而且观察发现是链头的行号。
然后考虑之后的行。在填了第一行之后有一些数被挤下去了，而这些挤下去的数是什么样子？
设一条链为 \((u_{i_1},v_{i_1})\cdots(u_{i_k},v_{i_k})\)，观察到在 \(P\) 中会留下 \(v_{i_k}\)，在 \(Q\) 中会留下 \(u_{i_1}\)，然后 \((u_{i_2},v_{i_1})\cdots(u_{i_k},v_{i_{k-1}})\) 下传到第二行。
我们设第一行的点构成的方阵为 \(M\)，下传到第二行的点构成的方阵为 \(N\)。
有了这些观察就可以证明性质 1 了。
正式证明里的正式证明。
\(P_M\) 第一行 \(=M\) 各链的链尾列号 \(=M^T\) 各链的链头行号 \(=Q_{M^T}\) 第一行。
\(Q_M\) 第一行 \(=M\) 各链的链头行号 \(=M^T\) 各链的链尾列号 \(=P_{M^T}\) 第一行。
巨大进步！我们已经证明了第一行是相等的。
一个强烈的想法是用归纳法。那我们就用归纳法。
把 \(P_M\) 的第一行去掉，会得到 \(P_N\)（根据定义）。
把 \(Q_M\) 的第一行去掉，会得到 \(Q_N\)（根据定义）。
根据上面两条，有：\(Q_{M^T}\) 的第一行去掉，会得到 \(Q_{N^T}\)。
根据归纳假设，\(P_N=Q_{N^T}\)，而 \(P_N\) 是 \(P_M\) 去掉第一行，\(Q_{N^T}\) 是 \(Q_{M^T}\) 去掉第一行。所以 \(P_M\) 和 \(Q_{M^T}\) 去掉第一行之后是一样的，而上面又证明了它俩的第一行是一样的，所以 \(P_M=Q_{M^T}\)。
对于 \(Q_M=P_{M^T}\)，证明类似，在此略去。
上面的证明和元素是否相等关系不大，套用证明的流程可以把有相等的情况证了。
性质 1 推论 1：因为 \(P_M=Q_{M^T}\)，所以如果 \(M\) 是对称方阵，\(P_M=Q_M\)。也就是每一个对称矩阵对应一个半杨表。
性质 1 推论 2：一个对称矩阵对应一个半杨表，那什么对应一个杨表呢？类似有 \(\pi=\pi^{-1}\) 的结论。这种排列叫做对合排列（involution），满足 \(\pi_i=j\iff \pi_j=i\)（\(i=j\) 允许）。
推论 2 应用：可以求杨表个数。大小 \(n\) 的杨表个数就是 \(n\) 长度的对合排列个数。
法一：这个个数就是 \(1\sim n\) 匹配的个数（不要求完美匹配）。记个数 \(a_n\)，有 \(a_n=a_{n-1}+(n-1)a_{n-1}\)，前一种是 \(1\) 不参与匹配，后一种是 \(1\) 选一个匹配。这样可以 \(O(n)\) 求杨表个数。
法二：这个个数就是由若干各环组成，每个环大小为 \(1/2\) 的图个数。可以用母函数：它的母函数是 \(e^{z+\frac{z^2}{2}}\)。
性质 2：若 \(\pi\) 对应 \((P_{\pi},Q_{\pi})\)，\(\pi^{R}=(\pi_n,\dots,\pi_1)\) 的主表为 \(P_{\pi}^T\)。
证明：
记杨表 \(S\) 行插入 \(x\) 的结果为 \(S\leftarrow x\)，列插入 \(x\) 的结果为 \(x\rightarrow S\)。
引理：\(y\rightarrow(S\leftarrow x)=(y\rightarrow S)\leftarrow x\)。（分类讨论可证，具体过程暂略）
记 \(S(x_1,\dots,x_n)=((x_1\leftarrow x_2)\leftarrow \cdots )\leftarrow x_n\)，\(S'(x_1,\cdots,x_n)=x_1\rightarrow (x_2\rightarrow \cdots(x_{n-1}\rightarrow x_n))\)。
根据归纳法易证 \(S(x_1,\dots,x_n)=S'(x_1,\dots,x_n)\)。
而 \(P_{\pi}=S(\pi_1,\dots,\pi_n)=S'(x_1,\dots,x_n)=(((x_n\leftarrow x_{n-1})\leftarrow\cdots)\leftarrow x_1)^T=P_{\pi^{R}}^{T}\)。
性质 3：\(P_\pi\) 列数 \(=|LIS(\pi)|\)，\(P_{\pi}\) 行数 \(=|LDS(\pi)|\)。
证明：
-
对于列数。
考虑这么一个 LIS 的贪心算法：从前往后扫，维护一个小根堆的序列。若当前数比当前末尾的堆顶大，新开一个堆；否则放入堆中。堆的个数就是 LIS 长度。容易发现这其实模拟了构造杨表的过程。
-
对于行数。
\(|LDS(\pi)|=|LIS(\pi^{R})|=P_{\pi^{R}}\text{宽度}=P_{\pi}^{T}\text{宽度}=P_{\pi}\text{高度}\).
性质 3 推论：在 \(\pi\) 中找 \(k\) 个不相交的 LIS，最长总长 \(=P_{\pi}\text{前 k 行总长}\)；找 \(k\) 个不相交的 LDS，最长总长 \(=P_{\pi}\text{前 k 列总长}\)。
证明太难，略。
快速求杨表
可以在 \(O(n\sqrt n\log n)\) 的复杂度内，根据一个排列 \(\pi\) 求出 \((P_{\pi},Q_{\pi})\)。
我们只需要考虑 \(P_{\pi}\) 即可，因为根据性质 1，\(Q_{\pi}=P_{\pi^{-1}}\)，用 \(\pi^{-1}\) 求一次 \(P\) 即可。
怎么求 \(P_{\pi}\)？
令 \(B=\lceil\sqrt n\rceil\)，则求这个杨表等价于求前 \(B\) 行和前 \(B\) 列。因为 \(P_{\pi}\) 不可能填到行列都 \(>B\) 的位置，否则 \(|P_{\pi}|>n\)。
我们只需要知道求前 \(B\) 行的方法，因为前 \(B\) 列等于 \(P_{\pi}^T\) 的前 \(B\) 行，根据性质 2 等于 \(P_{\pi^{R}}\) 的前 \(B\) 行。同样的方法再做一遍即可。
怎么求 \(P_{\pi}\) 的前 \(B\) 行？
直接暴力行插入，如果到达 \(>B\) 的行就直接退出。一次插入是 \(O(\sqrt n\cdot \log n)\)。（一共 \(B\) 行，每行内部二分）一共插入 \(n\) 次，复杂度 \(O(n\sqrt n\log n)\)。