OI

【模板】归并排序

归并排序、逆序对

求逆序对原理为：
对原序列进行归并排序，在每次合并两数组时可以直接统计逆序对的个数。针对左有序序列中的第i号元素，和右有序序列中的第j号元素，若存在 a[j] < a[i] ，则a[i]后的所有
元素都大于a[j]。这种情况下 逆序对的个数ans = mid - i + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int a[MAXN],t[MAXN],ans=0;
void mergesort(int a[],int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    mergesort(a,l,mid);
    mergesort(a,mid+1,r);
    
    int i=l,j=mid+1,k=l;
    
    while(i<=mid&&j<=r)
        if(a[i]<a[j]){
            t[k]=a[i];i++;k++;
        }
        else{
            t[k]=a[j];j++;k++;
            ans+=mid-i+1;//ans为逆序对个数
        }
    
    while(i<=mid){
        t[k]=a[i];k++;i++;
    }
    while(j<=r){
        t[k]=a[j];k++;j++;
    }
    
    for(i=l;i<=r;i++)
        a[i]=t[i];
}