我们考虑选中的 \(i\)，这个位置一定是 \(p_i>i\)，它想要往后走。而和它交换的 \(j\)，因为 \(\leq i\) 的有 \(i\) 个数，现在第 \(i\) 个位置已经被 \(p_i\) 占据了，所以 \(\leq i\) 的至少有一个在 \(i\) 后面所以和 \(p_i\) 交换的 \(p_j\) 一定 \(\leq i\)，也就是说，我们选中的 \(j\) 一定满足 \(p_j<j\)。
这启发我们将数分成两类，\(p_i>i\) 的和 \(p_i<i\) 的，交换只会在这两者之间进行。假设所有 \(p_i>i\) 的同时开始向右跑，所有 \(p_i<i\) 的同时开始向左跑，那么每对之间都会交换一次，总次数是不同类之间的逆序对数量。现在每类之间有先后交换的顺序，就考虑它的影响。对于两个属于第一类的 \(i,j,i<j\)，如果 \(p_i>p_j\)，那么 \(p_i\) 要比 \(p_j\) 先移动，并且必定恰好有一次是 \(p_i\) 原来在 \(p_j\) 左边，交换完之后到了 \(p_j\) 右边，使得有一个原来可以和 \(p_j\) 交换的二类不能和 \(p_j\) 交换，因此总的次数要减去一类间的逆序对，同理也要减去二类间的逆序对。
到这里已经可以做了，但是我们强行划分成两类不别扭吗？实际上稍微推一下式子就可以得到它其实是 \(\sum\limits_{i=1}^{n}{|i-p_i|}-\sum\limits_{i<j}[p_i>p_j]\)，于是就挺优美的。
标签：Sort,Bully,ip,交换,leq,CF1830E,逆序 From： https://www.cnblogs.com/275307894a/p/17484030.html