主要思路
显然在反串上建个 SAM 然后在 Link 树上跑个 DP 即可，然而数据很大，我们不能直接每个都暴力来求，那么我们就可以直接用虚树套一下即可。
好题好题。
我们发现每一个点向左、向右走都是有极限的，算出得到 \((x_i, y_i)\)，其中 \(x\) 代表左边、\(y\) 代表右边。那么，把这个东西放到散点图上，发现我们本质不同的操作是一个单调不降的折线图：因为如果我们把 \(x\) 作为这个路径的「最长向左移动距离」、\(y\) 作为这个路径的「最长向右移动距离」，那么这个折线经过某个点的 \(x\) 帧或是 \(y\) 帧都将导致这个东西 GG，所以我们计算这样的折线图就可以计算对应方案了。
我们可以直接用树状数组来进行转移即可。
想了半天都不知道怎么刻画状态，后面发现可以转成一个泛化问题，就比较好理解了。
考虑不严格地减去最小值、而是任意值，并达到题目要求的结果。这个问题肯定不会更优，而最优解可以直接作为本题最优解。
主要还是需要注意设计状态。
我们称 \((-1, x)\) 为单对，称 \((-1, -1)\) 为双对。我们可以试着从大到小填数字，这样就可以避免取 \(\min\) 的问题了。考虑 \(dp[i][j][k]\) 为选到第 \(i\) 个数字，然后有 \(j\) 个待处理、\(k\) 个单对待处理。转移的话，可以试着进行讨论。如果这个数字是某个单对之一，那么一种方式是啥都不干，还有一种是尝试进行匹配，\(j -= 1\)。如果不是单对之一，那么要么匹配、要么晾着。
最后乘上一个双对个数的阶乘，使其有序。
这题好神仙啊。
首先介绍一个暴力的套路（虽然跟正解没关系，但我觉得碰上很多比赛的时候会用上）：我们设置 \(f[i][j]\) 当前为前 \(i\) 个数中第 \(j\) 小的贡献，那么有
\[ f[i][j] = \begin{cases} \sum_{k = 1}^{i – 1} f[i – 1][k] (s_{i – 1} = <) \\ \sum_{k = i}^{j} f[i – 1][k] (s_{i – 1} = >) \end{cases} \]