排序（树状数组求逆序数+离散化）

传送门

逆序对指的是一个序列中有两个数ai和aj，i<j&&ai>aj，即它们下标与数值的增减不一致，那么对于这个问题：求一个序列中逆序对的个数，该如何解决呢？

树状数组求逆序的思想事实上和树状数组关系不大，以下图为例（自己画的，丑：）：

如上图，第一次将第一个数1对应的a[1]++，这时还看不出来，再将4对应的a[4]++，同理a[2]++……即将n对应的a[n]++，这样做，就可以将一个无序的序列变得有序，同时a数组也表示了对应下标的数是否出现/处理过，而且当只有i个元素变换之时，剩余元素不会对接下来的操作造成影响，现在给出计算到2时的图片：

那么，对于最新处理的2或任意一个n（设下标为i）来说，前i个数中，比它小及其本身的数的个数，就是前i项的前缀和，因为排在原序列中i之后的数尚未处理，而已处理的a中比他小的数必然在它前面，且对应a[]值为1，那么，已处理的i个数中，比这个数n大的数的个数，也就是这一个数的逆序对数，就是i-getsum(n)，而前缀和的求值与a数组的修改、维护，就可以交给树状数组了:

数据较大，需要离散化，单一数据离散化传送门

附上代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=5e5+50;

int num[maxn];
int temp[maxn];
map<int,int>mp;
int tree[maxn];

int lowbit(int p)
{
    return p&(-p);
}

void change(int p)
{
    for(;p<=maxn;p+=lowbit(p)){
        tree[p]++;
    }
}

int getsum(int p)
{
    int res=0;
    for(;p;p-=lowbit(p)){
        res+=tree[p];
    }
    return res;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&num[i]);
        temp[i]=num[i];
    }
    sort(temp,temp+n);
    int m=unique(temp,temp+n)-temp;
    for(int i=0;i<m;i++){
        mp[temp[i]]=i+1;
    }
//    for(int i=0;i<n;i++){
//        cout<<mp[num[i]]<<" ";
//    }
//    cout<<endl;
    ll ans=0;
    for(int i=0;i<n;i++){
        change(mp[num[i]]);
        ans=ans+i+1-getsum(mp[num[i]]);
    }
    printf("%lldn",ans);
    return 0;
}

最后

以上就是害怕酸奶为你收集整理的排序（树状数组求逆序数+离散化）的全部内容，希望文章能够帮你解决排序（树状数组求逆序数+离散化）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。