题解：AT_abc396_f [ABC396F] Rotated Inversions

· · 题解

原题传送门

求出原序列逆序对数量，开 m 个 vector 存每个值的出现位置。

把 k 增加的过程看做把原序列每个数加一再模 m 的过程。考虑求出每次改变增加或减少的逆序对数。

每次 k 增加，可能有一些点从 m-1 变成 0，只有这些点会影响逆序对数量。

通过 vector 求出这些点位置。由于这些点原本是序列中最大值，操作后变为序列中最小值，所以它们右边原本全都比它们小，左边操作后全都比它们大。减去右边数量加上左边的就做完了。

当然值一样的点永远不会产生逆序对，需要判断一下。