想象一下，冒泡排序交换的两个数一定是原数组的逆序对（反证容易证明：如果不是逆序对，相遇之后不会交换。两个数只有在相遇的时候才会使得下标相对大小互换，相遇之前一定是左的在左，右的在右。而不是逆序对的话，相遇的时候也不会交换，所以就一直不会交换）。
因为有序数组一定没有逆序对，所以逆序对一定换完了，所以swap次数就是逆序对总数。
我的写法是\(f_{i,j}\)，表示\(k\in [j,n]\)中\(a[k]<a[i]\)的\(k\)的个数。
交换次数就是\(f_{1,2}+f_{2,3}+...\)。（通过此式可以发现，如果\(a[x]<a[y],x,y\)，交换二者一定不优）
比如枚举交换的是\(x,y,x<y\)，那么\(x\)之前和\(y\)之后的点的\(f_{k,k+1}\)都没有改变，对交换次数贡献不变。
对于\(x\)和\(y\)，\(f_{y,y+1} \rightarrow f_{y,x+1} + [a[x]<a[y]?]\)，\(f_{x,x+1}\rightarrow f_{x,y+1}\)。
如果通过上面的式子退出来逆序对才要交换，\([a[x]<a[y]]=0\)。
现在关键是\([x+1,y-1]\)中的数的\(f_{k,k+1}\)又是如何变化的呢？
昨晚不知道怎么想的，用了权值树状数组查询一段值域的数的个数，其实完全不用。
\(a[k]>a[x]\)，则\(f_{k,k+1}\leftarrow +1\)。
\(a[k]>a[y]\)，则\(f_{k,k+1}\leftarrow -1\)。
也就是说，要知道\(k\in [x+1,y-1],a[k]>t\)的数的个数。
数据范围很小，再预处理一个\(g_{i,x}\)，表示\(k \in [1,i],a[k]>x\)的数的个数不就行了？
那对答案的贡献不就是\(g_{y-1,a[x]}-g_{x,a[x]}-g_{y-1,a[y]}+g_{x,a[y]}\)吗？
昨晚把上面的式子合并了，写成了\(a[y]<a[k]<a[x]\)，要\(-1\)，其实也可以写成\(a[k]<a[x]\)，减去\(a[k]<a[y]\)的。
然后再套一层前缀和预处理，就出来了。
标签：Sort,数组,交换,个数,相遇,Insertion,逆序 From： https://www.cnblogs.com/zhangchenxin/p/17806995.html