oneman233
2019-05-12 17:39:12
虽然用树状数组求逆序对这种方法发布在这道题这里显得有点大材小用，但我主要是想聊聊树状数组求逆序对的原理以及一个衍生的小问题。
首先来看看逆序对的定义
如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。
逆序对的一个应用是：数列中所有元素的逆序数之和等于交换相邻两数把数列变为有序的最小步数
是不是感觉与题意有些相似了？
接下来说说树状数组
树状数组是一个高效的求前缀和的数据结构，支持单点修改，关于它的更多信息请参看luogu树状数组模板：
P3368 【模板】树状数组 2
P3374 【模板】树状数组 1
既然可以求前缀和，我们不妨思考，如果我们把数据从大到小，按顺序在它的位置上加一，然后每插入一次就求一下该位置的前缀和，不就可以计算出这个数前面有多少个数字比他大了吗？
一个简单的实例：
测试样例中：4 3 2 1
我们按照刚才所说的步骤，首先按顺序由大到小在对应数字的位置上加一：
1、插入4，结果为1 0 0 0，ans=0
2、插入3，结果为1 1 0 0，ans=0+1=1
3、插入2，结果为1 1 1 0，ans=1+2=3
4、插入1，结果为1 1 1 1，ans=3+3=6
得出结果。
细心的同学们也许注意到了一个问题，数组有序是一个并不严格的定义，也就是说数组有从小到大和从大到小两个定义。而上题中我们所求的是从小到大的有序。
那么如果要求从大到小该如何是好？
答案很简单，改变逆序对的定义，找到一个数前面比它小的数有多少个即可，也就是说，在最后改变插入顺序为由小到大即可。
此外还有一点需要特别注意，在对数组进行排序是我们一定要使用稳定的排序算法，例如STL当中的stable_sort()，否则不稳定的排序算法可能会改变相同元素的相对位置，导致计算逆序数的时候出现错误！
上代码，关键点的注释已经写在其中：
#include <bits/stdc++.h>
using namespace std;
int n,ans=0;
int a[10005],b[10005],c[10005];
int lowbit(int x){return x&-x;}
void add(int x,int v)
{
while(x<=n){
a[x]+=v;
x+=lowbit(x);
}
}
int sum(int x)
{
int ans=0;
while(x>=1){
ans+=a[x];
x-=lowbit(x);
}
return ans;
}
bool cmp(const int &a,const int &b)
{
return a>b;
}
int main()
{
cin>>n;
for(int i=1;i<=n;++i)
cin>>b[i],c[b[i]]=i;
///稳定排序是为了防止有相同元素的情况，这可能导致答案出错
stable_sort(b+1,b+1+n,cmp);
///可在此处改变插入顺序
for(int i=1;i<=n;++i){
add(c[b[i]],1);
ans+=sum(c[b[i]]-1);
}
cout<<ans;
return 0;
}
一些碎碎念：
关于逆序对的更高效求法可以参看luoguP1908 逆序对
最后我想聊的是为什么逆序数之和就是我们的答案呢？
一个序列要有序，我们必须把最大的数放在序列末尾，然后就可以不再考虑它了，即数列元素个数从n变成了n-1，那么对一个给定的数字，要交换多少次才能把它放到合适的位置上呢？
应该是等到它右边比它大的数字全部有序之后这个数字才会被操作，此时它需要的交换次数就是它右边数字之和减去右边比他大的数字个数。