NOIP模拟赛20251106 T3

题目大意：

有一个长度为 \(n\) 的序列，每次你会单点修改，求每次修改完了之后的 \(f\)。
\(f\) 表示最少操作几次冒泡，使得他不降。
\(n,q \le 5 \times 10^5\)

解题思路：

考虑刻画这个东西，由于每次对于一个非前缀最大值的位置，恰好往前移动一格，所以设 \(f(i) = \sum_{j = 1}^{i - 1} [a_{j} > a_{i}]\)，那么答案就是求 \(max_{i = 1}^{n} f(i)\)。
但是这个东西是不好维护的，考虑换个角度。
就是变化量，如果 \(a_{i}\) 在整体中排 \(p\) 的话，就要从 \(i\) 移到 \(p\)，也就是 \(i - p\) 的最大值。
排名是可以直接维护的，所以就能权值线段树 \(O(n \log n)\) 了。