【BUAA 1246】行列の逆順のペア

配列内の逆順のペア
アルゴリズムを活用する前に先輩から聞いたのですが、これは逆順でいいです.ずっと自分で実現したことがないです.今回は試合中に試合をしなかったですが、自分で達成できました.とても達成感があります.帰りのアルゴリズムに対しても、徹底的に理解しました.多くのアルゴリズムは丸暗記ではなく、硬い暗記の前に時間をかけて忘れてしまいました.今回は徹底的にアルゴリズムの実行過程を理解しました.この問題を作るよりも、もっと貴重です.
コードは以下の通りです

#include <bits/stdc++.h>
#define LL long long

using namespace std;

int num[111111];
int n[111111];
LL sum;

void Merge(int l,int m,int r)
{
    int bg1 = l,bg2 = m+1,ed1 = m,ed2 = r;
    int i,k;
    for(k = l;bg1 <= ed1 && bg2 <= ed2; ++k)
    {
        if(num[bg1] > num[bg2])
        {
            n[k] = num[bg2++];
            sum += m-bg1+1;
        }else n[k] = num[bg1++];
    }
    while(bg1 <= ed1) n[k++] = num[bg1++];
    while(bg2 <= ed2) n[k++] = num[bg2++];
    for(k = l; k <= r; ++k)
        num[k] = n[k];
}

void MSort(int l,int r)
{
    if(l < r)
    {
        int m = (l+r)/2;
        MSort(l,m);
        MSort(m+1,r);
        Merge(l,m,r);
    }
}

int main()
{
    int t,n,i;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i = 0; i < n; ++i)
            scanf("%d",&num[i]);
        sum = 0;
        MSort(0,n-1);
        printf("%lld
",sum);
    }
    return 0;
}