题解：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$ 小的前缀最大值元素的和即可。