来解剖 来平息你的颤抖 叫嚷着还不足够 还需要更多疼痛 才值得温柔

test4

不要在意这个诡异的标题。

---

排序sort

快排的过程相当于以 \(a_r\) 为界限，更小的放到左边，更大的放在右边，我们还关心新的 \(a_r\) 是谁，左边是按顺序的填入，右边新的顺序只跟原本的顺序有关系素排列双射下去啦，所以就是唯一特定位置的值成为新的。

那么考虑 dp 一下 \(f[i][j]\) 表示长度为 \(i\) 做了 \(j\) 轮的方案数，枚举 \(a_r\) 大小 \(l\)，先选择左右边的位置 \(\binom{i-1}{l-1}\)，然后乘上左右的方案数 \(f[l-1][j-1]\times f[i-l][j-1]\) 即可。

---

染色col

\(a=b\) 显然是 \(2(n-1)-\max\{dis_i\}\)，十分经典。

\(a\neq b\)，要让 B 跟着 A 走，首先到中点会合最快，其次没必要为了最远点贡献走远（会 \(+1-1\)），算出 B 开始贡献的步数和点然后当 \(a=b\) 的问题再补全贡献即可。