归并排序逆序对+快读

归并排序原理

先对源数组拆拆拆！拆成最小的单个元素，再分别合并，合并时保证两数组有序（单元素有序，尽管非常平凡），
然后再一路合并下去，就得到有序的大数组了。
这种思想叫分治，就是"分而治之"

归并排序模版

使用前须将cnt置为0

void merge_sort(int *A,int x,int y,int *T,int &cnt)
{
    if(y-x>1)
    {
        int m = x+(y-x)/2;
        int p = x,q = m,i = x;
        merge_sort(A,x,m,T,cnt);
        merge_sort(A,m,y,T,cnt);
                //此时左半右半都有序
        while(p<m || q<y)
        {
            if(q >= y || (p<m && A[p]<=A[q])) T[i++] = A[p++];
            else {T[i++] = A[q++];cnt += m - p; }
        }
        for(int i = x;i < y;i++)A[i] = T[i];
    }
}

逆序对解释：

因为数组是从小到大复制的，从\(A[q]\)复制到\(T[i]\)时，左边还没来得及复制的那一些元素就是左边所有比\(A[q]\)大的数，此时只需要在左边加上\(m-p\)即可。

快读模版

inline int read()
{
    int x = 0,f = 1;char c = getchar();
    while(!isdigit(c)){if(c=='-')f=-1;else f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
inline void write_num(int x)
{
    if(x>9)write_num(x/10);
    putchar((x%10)+48);
}
inline void write(int x)
{
    if(x < 0)putchar('-'),x=-x;
    write_num(x);
} 

test

以下便是完整的代码，欢迎拍砖

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn],t[maxn];
void merge_sort(int *A,int x,int y,int *T,int &cnt)
{
    if(y-x>1)
    {
        int m = x+(y-x)/2;
        int p = x,q = m,i = x;
        merge_sort(A,x,m,T,cnt);
        merge_sort(A,m,y,T,cnt);
        while(p<m || q<y)
        {
            if(q >= y || (p<m && A[p]<=A[q])) T[i++] = A[p++];
            else {T[i++] = A[q++];cnt += m - p; }
        }
        for(int i = x;i < y;i++)A[i] = T[i];
    }
}
inline int read()
{
    int x = 0,f = 1;char c = getchar();
    while(!isdigit(c)){if(c=='-')f=-1;else f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
inline void write_num(int x)
{
    if(x>9)write_num(x/10);
    putchar((x%10)+48);
}
inline void write(int x)
{
    if(x < 0)putchar('-'),x=-x;
    write_num(x);
} 
int main()
{
    int n = read(),cnt = 0;
    for(int i = 0;i < n;i++)
        a[i] = read();
    merge_sort(a,0,n,t,cnt);
    write(cnt),putchar('\n');
    for(int i = 0;i < n;i++)
        write(a[i]),putchar(' ');
    return 0;
}