随便给出一组数据：
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\) 的数，其实我们可以
标签：P6186,NOI,后退,冒泡排序,数量,对块,逆序 From： https://www.cnblogs.com/zhangchenxin/p/16924076.html