NC15163 逆序数 归并

逆序对个数,可以归并,可以线段树(我不会)
注意开

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \
do { \
    cout << "\033[31;1m " << #x << " -> "; \
    err(x); \
} while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#endif

#ifndef debug
namespace FIO {
    template <typename T>
    void read(T& x) {
        int f = 1; x = 0;
        char ch = getchar();

        while (ch < '0' || ch > '9') 
            { if (ch == '-') f = -1; ch = getchar(); }
        while (ch >= '0' && ch <= '9') 
            { x = x * 10 + ch - '0'; ch = getchar(); }
        x *= f;
    }
};
using namespace FIO;
#endif


int n, m, Q, K, a[MAXN], tmp[MAXN];
ll ans;

void merge_sort(int lef, int rig) {
//    forarr(a, lef, rig);
    if(lef == rig) return ;
    int mid = (lef + rig) >> 1;
    merge_sort(lef, mid);
    merge_sort(mid+1, rig);
    int x = lef, y = mid + 1, i = 0;
    for( ; i<(rig-lef+1); i++) {
        if(x<=mid && y<=rig) {
            if(a[x] > a[y]) {
                ans += mid - x + 1; //统计答案
                tmp[i] = a[y++];
            } else
                tmp[i] = a[x++];
        } else {
            if(x <= mid) tmp[i] = a[x++];
            if(y <= rig) tmp[i] = a[y++];
        }
    }
    while(~(--i)) a[rig--] = tmp[i];
}

int main() {
#ifdef debug
    freopen("test", "r", stdin);
    clock_t stime = clock();
#endif
    read(n);
    for(int i=1; i<=n; i++) read(a[i]);
    merge_sort(1, n);
//    forarr(a, 1, n);
//    show(ans);
    printf("%lld\n", ans);



#ifdef debug
    clock_t etime = clock();
    printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
    return 0;
}