主要思路
想了半天都不知道怎么刻画状态，后面发现可以转成一个泛化问题，就比较好理解了。
考虑不严格地减去最小值、而是任意值，并达到题目要求的结果。这个问题肯定不会更优，而最优解可以直接作为本题最优解。
想了半天都不知道怎么刻画状态，后面发现可以转成一个泛化问题，就比较好理解了。
考虑不严格地减去最小值、而是任意值，并达到题目要求的结果。这个问题肯定不会更优，而最优解可以直接作为本题最优解。
为啥我看到了 C# 代码（那是我逝去的青春）。
首先知道肯定是 SAM，但是你我都知道在线性构造的时候树的形态会变，所以没法维护根点权值和。所以加上一个 LCT 弄一下即可。
主要还是需要注意设计状态。
我们称 \((-1, x)\) 为单对，称 \((-1, -1)\) 为双对。我们可以试着从大到小填数字，这样就可以避免取 \(\min\) 的问题了。考虑 \(dp[i][j][k]\) 为选到第 \(i\) 个数字，然后有 \(j\) 个待处理、\(k\) 个单对待处理。转移的话，可以试着进行讨论。如果这个数字是某个单对之一，那么一种方式是啥都不干，还有一种是尝试进行匹配，\(j -= 1\)。如果不是单对之一，那么要么匹配、要么晾着。
最后乘上一个双对个数的阶乘，使其有序。
比较显然，我们需要选两个点集，最后贡献就是两个点集的极差积。排个序，并且把每个长度为 \(n\) 的区间都给做一遍即可。
写起来还是有点麻烦的，LCT + 离线处理放在一起就比较难写。
首先我们可以考虑离线，这样我们就可以分颜色来考虑这个问题。假设现在在颜色 \(c\)，那么我们需要统计每个时刻不包含本颜色的路径数量，并且做差分（也就是做每个时刻）。此时颜色只分黑白，那么我们只需要把本颜色的点做成白色，然后统计每个黑点的连通块大小的平方即可。