CF1637H Minimize Inversions Number

我直接？？？？？？？？？？？？？？？？？？

考虑一个数怎么做，就是逆序对减去一个 \(i\) 前面的逆序对再加上顺序对。考虑很多数怎么做，就是这个玩意的和再加上子序列种的顺序对减去逆序对，顺序对可以用逆序对表示，现在只考虑顺序对。

注意到，如果 \(i<j,p_i>p_j\) 且 \(i\) 在子序列中 \(j\) 不在子序列中，那么把 \(j\) 弄进来 \(i\) 拿出去一定不劣。证明显然，但我也不知道这是怎么注意到的。

于是式子可以写成 \(\sum...+\binom{k}{2}-\sum_{i=1}^{k}\sum_{j\ge q_i}[p_{j}>p_{q_i}]\)。稍微归一下类贪心即可。