T2.冒泡排序

题面：

给定一个 $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])

$n,m\le 2\times 10^5$，$0\le k\le 2^{31}-1$。

举例/说明：

对于序列 $\{3,2,1\}$，进行第一轮冒泡排序后变成：$\{2,1,3\}$，进行第二轮冒泡排序变成：$\{1,2,3\}$，此后不再有变化。

注意询问操作之后不改变原始序列。

解答：

$\texttt{Solution 1}$

$\text{20 pts}$

首先，一种很容易想到的方法就是暴力解决，每次按照题目模拟即可。一种可以优化的方法就是，因为冒泡排序进行 $n-1$ 轮就已经排好序了，所以说当 $k\ge n$ 时直接输出 $0$ 即可。

需要注意的是，询问操作不对原序列产生影响，所以需要另外开一个数组进行冒泡排序操作。交换操作时间复杂度 $O(1)$，询问操作时间复杂度 $O(n^2)$，所以整体的时间复杂度 $O(n^3)$。

显然，这种方法是不可行的。

$\texttt{Solution 2}$

$\text{40 pts}$

现在我们来想一想更好的解法。如果题目中没有交换操作，并且 $k$ 取遍 $0$ 到 $n-1$ 呢？易知，这种情况是一定存在的，所以我们必须要首先初始化这样的情况。

假设 $k_i$ 为进行第 $i$ 轮冒泡排序操作减少了多少组逆序对。可以知道，每交换一次，逆序对个数减少 $1$。所以说 $k_i$ 就等于一次冒泡排序时 swap() 执行的次数。

经过观察可以得出，每次冒泡排序时，如果一个数前面没有比它大的数了，那么它这一轮就不会向前移。否则，它就会向前移一位。而向前移一位，相当于就贡献了一次 swap()。设这一轮没有向前移的数的个数为 $x$ 个，那么向前移一位的数的个数就是 $n-x$ 个，即 $k_i=n-x$。所以现在我们要做的事情就是统计 $x$。

我们观察序列中的第 $i$ 个数，设前面比它大的数的个数为 $v_i$。首先处理 $v$ 数组用树状数组即可解决，时间复杂度 $O(n\log n)$。对于这个数，前 $v_i$轮它都会向前移一位。为什么呢？对于每一个在它前面且比它大的数，都会在不同轮"碾压"它一遍，也就是经过它。这就消耗了 $v_i$ 轮，而在第 $v_i+1$ 轮时，这个数前面没有比它大的数了，此时将其统计在 $x$ 中。

总结一下，如果 $v$ 数组中有 $x$ 个数小于等于 $i$，那么 $k_{i+1}=n-x$。

处理完 $k$ 数组之后，若要求 $t$ 轮过后逆序对的个数，即为起始的逆序对个数再减去 $\sum\limits_{i=1}^t k_i$。对于起始逆序对个数和 $k$ 数组求和，都可以用树状数组优化。

对于每一个交换操作，重新处理一遍 $k$ 数组即可，总体时间复杂度 $O(n^2\log n)$。因为 $5-6$ 测试点中交换次数不超过 $100$，所以也可以通过这道题。

$\texttt{Solution 3}$

$\text{100 pts}$

你可能会觉得，最后处理交换操作的方式也太粗暴了吧。没错，思路坏就坏在了这里。然后你尝试着找一找 $k$ 数组变化的规律。经过尝试多组数据后，你发现：天哪！对于每次的交换，$k$ 数组的值只有一个变化了！重新处理一边的话，是不是有点太不恰当了？

好，这就是我们要研究的地方：对于每次交换操作，哪个 $k_i$ 被修改了？

设被交换的两个数是 $p_i,p_{i+1}$。如果交换前的 $p_i<p_{i+1}$，那么逆序对个数增加了 $1$，$k_i$ 增加 $1$；否则，逆序对个数减少 $1$，$k_i$ 减少 $1$。

我们先研究 $p_i<p_{i+1}$ 的情况。交换之后，易得在前 $v_{i+1}$ 轮这两个数的方位不会发生变化。而在第 $\text{Round}=v_{i+1}+1$ 轮时，就轮到 $p_{i}$ 交换了，此时 $k_{\text{Round}}$ 就会增加 $1$吗？当然不是！如果之前有数介于 $p_i$ 和 $p_{i+1}$ 之间，那么交换两数之后，这个数和 $p_i$ 就不会进行交换，此时 $k$ 数组仍然不变。所以说，$\text{Round}$ 应该等于 $v_i+1$。

同理，对于 $p_i>p_{i+1}$ 的情况，相当于换回来，$k_{v_{i+1}}$ 减少 $1$。

这样我们就处理好了 $k$ 数组，注意还要更新 $v$ 数组哦！

综上，交换和查询的时间复杂度都是 $O(\log n)$，所以总体复杂度就是 $O(n\log n)$，足以解决这道题。