Luogu6186 [NOI Online #1 提高组] 冒泡排序

题意：给定一个 的排列 ，接下来有 次操作，操作共两种：

1. 交换操作：给定 ，将当前排列中的第 个数与第 个数交换位置。
2. 询问操作：给定 ，请你求出当前排列经过 轮冒泡排序后的逆序对个数。

，时限 。

---

设 表示 前面比 大的数的个数，显然，逆序对总数即为 。

手玩冒泡排序可以发现，每一轮排序中，各个 恰好减少 。

• 证明：若 之前已经有序 ，则显然 处没有交换。

  反之，最大值会上浮， 处必有一次交换，则 。

最终的答案即为：

用树状数组维护值与个数即可。注意特判 的情况。

当交换两个数时，会触发 次单点修改。

复杂度 。