\(\texttt{Sol. Luogu P6186}\) [NOI online #1 提高] 冒泡排序

太毒瘤啦！！！果然是我太菜（水）了......

题目描述

给定一个 \(1 ∼ n\) 的排列 \(p_i\)，接下来有 \(m\) 次操作，操作共两种：

1. 交换操作：给定 \(x\)，将当前排列中的第 \(x\) 个数与第 \(x+1\) 个数交换位置。
2. 询问操作：给定 \(k\)，请你求出当前排列经过 \(k\) 轮冒泡排序后的逆序对个数。
   对一个长度为 \(n\) 的排列 \(p_i\) 进行一轮冒泡排序的伪代码如下：

for i = 1 to n-1:
  if p[i] > p[i + 1]:
    swap(p[i], p[i + 1])

思路：

很显然，我们必须先思考有关冒泡排序的本质，获得相关性质，才能继续做题。

所以这个本质是什么呢？

干想了一会，啥也没想出来，就举个例子：

\(\text{4 3 5 2 1}\to\text{3 4 2 1 5}\)

大概能发现，一个数能往后交换，仅当它左边已经没有了比他大的数。这样，它才能往后交换，去“消灭”逆序对。开始时，一个数的前面有多少个大于它的数，它就要被交换多少次，本轮就不能发挥它的作用。当前轮有 \(x\) 个能交换的数，就有 \(n-x\) 个逆序对被消灭。一个数的前面有 \(t\) 个比他大的数，这个数在 \(t+1\) 轮排序才会往后交换。

我们要求的，是冒泡排序进行 \(k\) 轮后逆序对的个数，那就把不修改的情况预处理出来，再考虑修改对答案带来的影响。

记 \(a[i]\) 为原数列， \(b[i]\) 为 \(a[i]\) 前面有多少个数比他大。将 \(\{b\}\) 丢进一个桶里（\(h\)），在这个桶上建立树状数组求前缀（因为对于\(b\)中的非零数来说每轮被交换一次，每轮是要\(-1\)的，故当前 \(b\) 中 \(0\) 的个数再拿 \(n\) 减就是本轮逆序对减少的数量，所以是求前缀）就可以预处理出第 \(i\) 轮减少的逆序对个数。

然后就是考虑修改带来的影响。

容易发现，相邻的两项交换，对整体逆序对个数的影响只能是 \(+1(a_x<a_{x+1})\) 或 \(-1(a_x>a_{x+1})\) 。以 \(+1\) 为例，这个变换在序列 \(\{b\}\) 中的影响就是 \(b_{x+1}+1\) 。在 \(b_{x+1}\) 这一项 \(+1\) 后，即 \(b_{x+1}\) 执行冒泡后，剩余部分和未交换的结果就是一样的了。

$$\left[\begin{matrix}a:&4&3&5&2&1\ b:&0&1&0&3&4\ h:&2&1&0&1&1\end{matrix}\right]\ \overset{\text{Exchanging a[2]&a[3]}}{\longrightarrow} \ \ \left[\begin{matrix}a:&4&5&3&2&1\ b:&0&0&2&3&4\ h:&2&0&1&1&1\end{matrix}\right]$$

根据“当前轮有 \(x\) 个能交换的数，就有 \(n-x\) 个逆序对被消灭”这句话，我们用 \(n(=5)\) 依次减 \(\{h\}\) 的前缀和，得到每轮减少的逆序对个数：

原来：\([2,1,0,1,1]\to[3,2,2,1,0]\)

之后：\([2,0,1,1,1]\to[3,3,2,1,0]\)

对这个新得出来的序列再做前缀和。容易发现，做完前缀和后交换操作可以很方便维护。当然，因为我们要的是 \(k\) 趟冒泡排序后的结果，所以这个答案序列是要不断单点更新 + 求前缀和的，用树状数组维护。

（大概是对的吧...？）代码明天写。

为什么想不出来？\(\huge\text{思维浅了！}\) 或者是 \(\huge\text{模拟能力不够？}\)