51nod 1019 逆序数 (树状数组)

小咪咪 2022-07-14 00:45 178阅读 0赞

[1019 逆序数][1019] ![ok.png][]

基准时间限制：1 秒 空间限制：131072 KB 分值: 0 [难度：基础题][Link 1]

![star.png][] 收藏

![plus.png][] 关注

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。

Input

第1行：N，N为序列的长度（n <= 50000)
    第2 - N + 1行：序列中的元素（0 <= A[i] <= 10^9）

Output

输出逆序数

Input示例

4
    2
    4
    3
    1

Output示例

关于逆序数和本题分析：

http://blog.csdn.net/acm\_hmj/article/details/53263971

关于树状数组：

http://blog.csdn.net/acm\_hmj/article/details/53223678

#include <iostream>
    #include <algorithm>
    #include <cstring>
    #define maxn 50005
    using namespace std;
    long long n,k;
    long long b[maxn]; // 1 1 1 1
    long long c[maxn]; // 1 2 1 4
    
    
    struct node
    {
        long long val;//数值
        long long id; //位置
    } a[maxn];
    
    bool cmp(node x,node y) //按照数值排序
    {
        return x.val<y.val;
    }
    
    int Lowbit(int n)
    {
        return n&(-n);
    }
    
    int sum(int n) //求和
    {
        int ans=0;
        while(n>0)
        {
            ans+=c[n];
            n-=Lowbit(n);
        }
        return ans;
    }
    
    void Change(int pos,int num) //修改
    {
        while(pos<=n)
        {
            c[pos]+=num;
            pos+=Lowbit(pos);
        }
    }
    
    int main()
    {
        while(cin>>n)
        {
            for(int i=1; i<=n; i++)
            {
                cin>>a[i].val;
                a[i].id=i;
                b[i]=1;
            }
    
            for(int i=1; i<=n; i++)
            {
                c[i]=0;
                for(int j=i-Lowbit(i)+1; j<=i; j++)
                    c[i]+=b[j]; //b的数状数组
            }
    
            sort(a+1,a+n+1,cmp);
            k=0;
            for(int i=1; i<=n; i++)
            {
                k+=sum(a[i].id-1);
                Change(a[i].id,-1);
            }
            cout<<k<<endl;
        }
        return 0;
    }

[1019]: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1019
[ok.png]: http://file.51nod.com/images/icon/ok.png
[Link 1]: http://www.51nod.com/onlineJudge/problemList.html#!groupId=1
[star.png]: http://file.51nod.com/images/icon/star.png
[plus.png]: http://file.51nod.com/images/icon/plus.png