题解：P12865 [JOI Open 2025] 冒泡排序机 / Bubble Sort Machine

· · 题解

众所周知，冒泡排序的过程是能维护的。

不妨假设 a_i 互不相同，否则可以做微小扰动。

具体地，假设 p_i=\sum_{j<i}[a_j>a_i]，即 i 前面的比他大的数的个数。那么前 p_i 轮 a_i 肯定是往前移（比它大的要超过他）。然后在后面的轮，a_i 肯定一直是前缀最大值。

把询问变成两个前缀作差，我们把元素分成两类。一类是前缀最大值，一类是非前缀最大值。

对于非前缀最大值，处理是简单的。这些元素一直在减少，每次都在整体往前移动。用个树状数组就得了。

然后是前缀最大值元素。我们每轮冒泡排序都会加入新的前缀最大值。

假设当前前缀最大值的下标是 i_1<i_2<\dots<i_k。那么冒泡一轮之后就会变成：i_2-1,i_3-1,i_4-1,\dots,n。

也就是，前缀最大值下标（注意，我们不关心元素具体值）的变化过程大概就是每次向前整体移动 1，然后再加上 n。

由于前缀最大值元素是单调上升的，于是我们可以用线段树算出这个前缀有多少个前缀最大值元素（记为 k），然后用值域线段树算出前 k 小的前缀最大值元素的和即可。