P9596 [JOI Open 2018] 冒泡排序 2 做题记录

P9596 [JOI Open 2018] 冒泡排序 2 做题记录

P9596 [JOI Open 2018] 冒泡排序 2 / Bubble Sort 2 - 洛谷 (luogu.com.cn)

Solution 1

结论：设 \(v_i=\sum_{j\le i} [a_j>a_i]\)，序列 \(a\) 的代价为 \(\max\{v_i\}\)。

对每个位置考虑，前面比它大的移到它后面之后才能轮到 \(i\) 向后移动，然后轮到它时后面如果有比它小的还需要移动一轮，所以 \(v_i=\sum_{j\le i} [a_j>a_i]+[a_i>(\min_{j>i} a_j)]\)。

然后发现如果 \(i\) 后面有比它小的 \(i\) 一定不优，所以后面一项可以去掉，\(v_i=\sum_{j\le i} [a_j>a_i]\)。

这个代价还是不好算，但由于只有后缀最小值有用，所以将 \(v_i\) 继续改为 \(\sum_{j=1}^n [a_j>a_i]-(n-i)\)，这个就好维护了，上权值线段树即可。

Solution 2

结论：设 $a_i $ 排序后应该在的位置为 \(p_i\)，则代价为 \(\max\{i-p_i\}\)。

若 \(a_i\) 不是后缀最小值，那么它的 \(i-p_i\) 一定不优。

首先若 \(i<p_i\)，那么它一定不会移动到 \(p_i\) 的右边，轮到它移动时一定已经归位，代价为 \(0\)。

然后若 \(i>p_i\)，那么前面比它大的位置向后移动时，一定恰好让它向前移动一个，轮到它移动时一定已经归位。

\(p_i\) 即为 \(a_i\) 在全局的排名，维护 \(i-p_i\) 的最大值，平衡树维护。

两个结论其实本质一样，殊途同归了。