题解

思路

对值 $x$，记它在初始排列左侧比它大的元素个数为 $inv_x$。

做法

一次覆盖到 $x$ 的前缀冒泡操作会让其中一个较大元素越过 $x$，所以只要其贡献仍为正，它对总逆序数的贡献就恰好减少 $1$。由于 $A$ 非降，若 $x$ 的初始位置为 $pos_x$，它从第一个满足 $A_i\ge pos_x$ 的操作起会一直被覆盖，因此贡献会在一段连续的操作编号上逐次减一。

用树状数组按初始排列顺序求出全部 $inv_x$ 与初始逆序数，用二分查找求每个值首次被覆盖的编号，再在这段连续编号上对“本次减少量”做差分。

复杂度

前缀累加差分并从当前逆序数中扣除即可依次输出答案，时间复杂度为 $O(N\log N+N\log M+M)$，空间复杂度为 $O(N+M)$。