给定长度为 $n$ 的序列 $a$。
定义一轮排序为：从前往后比较相邻的两个数，若前面的数大于后面的数，则交换这两个数。
进行 $q$ 次单点修改，每次修改后，回答当前序列需要几轮排序才能变成一个不下降序列。
$n, q \leq 500000$。
题解
- 观察一轮排序的过程，不难发现：每一轮中，对于任意数字 $a_i$，若存在 $a_p$ 使得 $a_p > a_i$ 且 $p < i$，则满足条件的最大的 $a_p$ 会被移到 $a_i$ 的后面。
- 故答案应为 $\max_{i=1}^{n} (a_i\text{ 前面比 } a_i \text{ 大的数的个数})$。
- 可用 K-D Tree 或者树套树维护答案，时间复杂度两个 $\log$，常数小可能能过。
- 注意到“前面”这个条件很烦，考虑转化掉这个条件。
- 将答案改写为 $\max_{i=1}^{n} (i-a_i\text{ 前面 }\leq a_i \text{ 的数的个数})$。
- 考查序列中两个元素 $a_x, a_y$，其中 $x < y, a_x \geq a_y$ 时，可以发现：若去掉“前面”这个条件，那么 $a_x$ 处的答案会被多减，导致不优。但 $a_y$ 的答案一定比 $a_x$ 优，$a_x$ 一定不会成为答案。
- 故可将答案改写为 $\max_{i=1}^{n} (i-\leq a_i \text{ 的数的个数})$。
- 离线使用权值线段树维护即可。
- 时间复杂度 $O((n+q) \log (n+q))$。
由于某些原因，暂时不给出代码。