P1908 逆序对

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//Inverted Sequence Numbers

//different from only Merge Sort:"//Diff" 

#include<bits/stdc++.h>
using namespace std;
const int MAXn=500000;

inline int read(){
    register char c;
    while(c=getchar(),c<'0'||c>'9');
    register int x(c-'0');
    while(c=getchar(),c>='0'&&c<='9') {
        x=x*10+c-'0';
    }
    return x;
}

int n;
int a[MAXn+10];
int tmp[MAXn+10];
long long ans;//Diff
void merge(int ll, int rr) {
    if (rr - ll <= 1) {
        return;
    }
    int mid = ll + (rr - ll >> 1);
    merge(ll, mid);
    merge(mid, rr);
    int p = ll, q = mid, s = ll;
    while (s < rr) {
        if (p >= mid || (q < rr && a[p] > a[q])) {
            tmp[s++] = a[q++];
            ans += mid - p;//Diff
        } else {
            tmp[s++] = a[p++];          
        }
    }
    for (int i = ll; i < rr; i++) {
        a[i] = tmp[i];
    }
}

int main() {
    n = read();
    for (int i = 0; i < n; i++) {
        a[i] = read();
    }
    merge(0, n);
    printf("%lld", ans);//Diff
}