题解 P1908 【逆序对】

· · 题解

好像大部分人都是利用归并排序做的

那么我讲一下树状数组的逆序对吧

正常的暴力思路我就不讲了

另类的暴力思路（20分）：桶排思想，每拿到一个值放入桶中，统计所有大于这个数的数量，然后累加

优化：离散化，因为n<=40000，所以只需要存那个数在数组中是第几大就好了。（然而并没有什么用）离散代码片段:

bool cmp1(const int &x,const int &y)
{
    return b[x]>b[y];  //对编号进行排序
}
int main()
{
    int ans=0;
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)
    {
        scanf("%d",&b[i]);  //读入
        a[i]=i;//顺便初始化一下
    }
      sort(a+1,a+n+1,cmp1);  //排序
    //这里略过接下来的部分，a[]就是我们要用的"第几大"数组
}

正解（100分 56ms 2MB）：树状数组

由暴力思路2，我们发现需要不断的求和和修改，所以引出树状数组，建议大家在手上模拟一遍

如样例：

设b[]为读入的数组，a[]为要离散化后的数组，C[]为树状数组，A[]为树状数组对应对数组（被求和的数组），sum(x)为求\sum_{i=1}^{x}A_i（前A数组中前x个的和）

6

5 4 2 6 3 1

1)进行离散化操作，处理数据（这里储存的是在数组中是第几大的）：a[]={2,3,5,1,4,6}

2)然后加入 a_1=2 ans=0，目前数组中小于a1的全部可以和a1组成逆序对

3)加入 a_2=3 ans=1 同上

4)加入 a_3=5 ans=3

5)加入 a_4=1 ans=3

6)加入 a_5=4 ans=6

6)加入 a_6=6 ans=11

8)输出ans

代码：

#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,c[40005]={0},a[40005]={0},b[40005]={0};  //定义数组，b[]为读入的数组，a[]为要离散化后的数组，C[]为树状数组
inline void Add(register int x)  //树状数组加入
{
    for(;x<=n;x+=(x&-x))
        c[x]++;  //因为这里只需要1，所以我就写出c[x]++了
}
inline int Sum(register int x)  //树状数组求和，同上面的sum(x)
{
    register int s=0;  //计数的变量
    for(;x>0;x-=(x&-x))  //累计
        s+=c[x];
    return s;  //返回结果
}
bool cmp1(const int &x,const int &y)  //离散化需要用的，上面有讲
{
    return b[x]>b[y];
}
int main()
{
    int ans=0;  //ans为最后的结果
    scanf("%d",&n);  //读入n
    for(register int i=1;i<=n;i++)
    {
        scanf("%d",&b[i]);  //读入
        a[i]=i;  //顺便初始化一下a数组
    }
    sort(a+1,a+n+1,cmp1);  //给a数组排序，达到最终的效果
    for(register int i=1;i<=n;i++)
    {
        Add(a[i]);  //依次加入树状数组
        ans+=Sum(a[i]-1);  //计算结果并累计
    }
    printf("%d",ans);  //输出ans
    return 0;  //返回
}