P8449 [LSOT-1] 逆序对 题解

· · 个人记录

我们考虑到当序列中数互不相同时，交换任意两个数都会使逆序对的奇偶性变化。若 a_i \lt a_j, i\lt j 交换，那么交换后逆序对数量加一；否则，逆序对数量会减一。

因此我们可以考虑把操作一和二转化为交换操作。

二操作其实可以转化为交换区间 [l, r] 和 [r + 1, k]。

我们考虑一操作。

我们发现，[l_1, r_2] 以外的部分，是不会受到影响的，因为只是这个区间之内的相对位置发生了改变。

具体来说，[l_1, r_1]，[r_1 + 1, l_2 - 1] 和 [l_2, r_2] 内部的逆序对也没有变化。

因此，实际上我们进行的操作就是把这几个区间之内的数按序交换。交换的总数是 L_1L_2 + L_1L_3 + L_2L_3，其中 L 是每个区间的长度。

三四操作是显然的。

因此我们判断它的奇偶性，这个题就做完了。