逆序数

题目链接：https://www.luogu.org/problem/P1908
题目链接：https://ac.nowcoder.com/acm/problem/15163
题意：给n个数，求这n个数的逆序对。（$a_i$<$a_j$&&i>j）

归并排序做法：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=5e5+5;
int n;
int a[MAX_N];
int b[MAX_N];
ll ans=0;

void mergesort(int s,int t){
    if(s>=t) return;
    int mid=(s+t)>>1;
    mergesort(s,mid);
    mergesort(mid+1,t);
    int i=s;int j=mid+1;int k=s;
    while(i<=mid&&j<=t){                //合并两个区间
        if(a[i]<=a[j]) b[k++]=a[i++];   //满足顺序，直接用b数组存储
        else {b[k++]=a[j++]; ans+=mid+1-i;}  //当第一个区间的数比第二区间的数大，则它的逆序数为mid+1-i,i为这个数在第一个区间的位置.
    }
    while(i<=mid) b[k++]=a[i++];
    while(j<=t) b[k++]=a[j++];
    for(int l=s;l<=t;l++) a[l]=b[l];
}

int main() {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    mergesort(1,n);
    printf("%lld\n",ans);
	return 0;
}

树状数组做法：

1.首先我们要知道树状数组是可以用来维护前缀和;

2.我们利用桶排的思想来求逆序对数,即遍历数组a,然后用b数组存储a[i]出现的次数(b[a[i]]++)。对于每个a[i]来说，它的逆序数为i-(1~$b_i$)的前缀和；如果直接遍历b的话太慢，所以我们用树状数组来维护前缀和。

3.当n很大的时候，我们不足以开这么大的b数组来存储，于是我们可以对a数组进行离散化，先将a数组排序，然后用1~n来表示a数组的相对大小。

4.要注意出现相同的数的时候，我们要将出现在后面的数排在后面。不然$a_i$=$a_j$ && i < j的时候，排序可能会让$a_j$排在$a_i$前面，导致处理$a_i$时会将$a_j$误判为逆序对.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=5e5+5;
int n;
int a[MAX_N];
int b[MAX_N];
int tree[MAX_N];
struct Node
{
    int index;
    int val;    
}node[MAX_N];   //用结构体来存储原来的值和位置


inline int lowbit(int x)       
{
    return x&(-x);
}


inline bool cmp(Node x,Node y)      //排序法则
{
    if(x.val==y.val)return x.index<y.index;
    else return x.val<y.val;
}

 void add(int i,int x)        //给第i位数加x
{
    while(i<=n)
    {
        tree[i]+=x;
        i+=lowbit(i);
    }
}

 int sum(int i)         //求1~i的前缀和
{
    int s=0;
    while(i>0)
    {
        s+=tree[i];
        i-=lowbit(i);
    }
    return s;
}


int main() {
    scanf("%d",&n);
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&node[i].val);
        node[i].index=i;
    }
    sort(node+1,node+1+n,cmp);  //排序
    for(int i=1;i<=n;i++) b[node[i].index]=i;   //离散化  
    for(int i=1;i<=n;i++)
    {
        add(b[i],1);        
        ans+=i-sum(b[i]);
    }
    printf("%lld\n",ans);
	return 0;
}

后记

因为树状数组要排序，复杂度已经O(nlogn)了，还要进行维护树状数组操作，在数比较大的时候会比归并慢。
但如果n比较小的情况下，用树状数组做会比较快，不用离散化的情况下。