冒泡排序交换次数就是逆序对个数，设每个位置的数字向前形成的逆序对是 \(c_i\)，那么有序即 \(c_i=0\) 对每个 \(i\) 都成立，考虑冒泡中一次交换 \((i,i+1)(a_i>a_{i+1})\) 对 \(c\) 的影响，那么就是 \(c_i\leftarrow c_{i+1}-1,c_{i+1}\leftarrow c_i\)，全局逆序对 \(-1\)。
[USACO18OPEN] Out of Sorts S
求数组最少经过多少轮冒泡后才能有序，这里冒泡是从前往后扫的。
考虑一轮冒泡是什么样子的：选一些数把它们往后移动到某个位置，其他的相对位置不变，并且移动的区域没有交，那么一个数被移动仅当 \(c_i=0\) 否则前面会有一个数覆过它，然后一个数从 \(i\) 移到 \(j\) 就使得 \(c_{i+1},c_{i+2},\cdots,c_j\) 前移一位并 \(-1\)，所以 \(c_i\leftarrow\max\{c_{i+1}-1,0\}\)，从宏观上来说就是所有 \(c_i\) 减少 \(1\)，因此答案是 \(\max\{c_i\}\)。
[NOI Online #1 提高组] 冒泡排序
有了上一题的结论这个题水到爆，用树状数组维护所有 \(c_i\) 就可以了。