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

随便给出一组数据：

5 3 1 2 4

初始逆序对数量： \(6\)。

冒泡排序

一轮：3 1 2 4 5 \(6-4=2\)。
两轮：1 2 3 4 5 \(2-2=0\)。

观察会发现，数 \(x\) 会一直后退，直到有一个大于 \(x\) 的数 \(y\)，\(y\) 也会一直后退……

逆序对的数量就是所有后退数 \(x\) 后退的长度之和。

由于一直后退，直到遇到一个更大的后退数，所以长度之和就是 \(n – cnt(x)\) 。

那么问题来了，如何统计后退数数量呢？

一个直观的想法是，后退数将区间划分成了一个个逆序对块。

上图是序列中数的大小的柱状图，其中，不同颜色分别代表了不同逆序对块（黑色的不是）。

我们要做的，就是统计逆序对块的数量，或者说，是每个逆序对块中最大的数的数量。

题解中都是观察到了最大的数 \(a[x]\) 是 \(max(a[i]), i \in [1, x]\)这个特点，然后用在值域上建立树状数组统计每个数前面有多少个数比自己大，记为 \(f[x]\)。

第一轮冒泡，后退数是 \(f[x] = 0\) 的数。

排序完之后，所有逆序对块中的、除了第一个的数的 \(f[y]\) 都要减一，这是因为 交换是只发生在逆序对块中的。

第二轮冒泡，后退数是 \(f[x] = 0或1\) 的数，其实我们可以

原文地址：http://www.cnblogs.com/zhangchenxin/p/16924076.html