上交oj1219 2018计算机学科夏令营上机考试 E:重要逆序对

http://bailian.openjudge.cn/xly2018/E/

#include <bits/stdc++.h>
using namespace std;
int visited[30];
long long ans = 0;
int n;
int a[500005];
int temp[500005];
void Merge(int a[],int l1,int r1,int l2,int r2){
    int i = l1;
    int j = l2;
    while(i <= r1 && j <= r2){
        if(a[i] <= a[j]){
            i++;
        }
        else{
            ans += (r1-i+1);
            j++;
        }
    }
    i = l1;
    j = l2;
    int cnt = 0;
    while(i <= r1 && j <= r2){
        if(a[i] < a[j]){
            temp[cnt++] = a[i];
            i++;
        }
        else{
            temp[cnt++] = a[j];
            j++;
        }
    }
    while(i <= r1) temp[cnt++] = a[i++];
    while(j <= r2) temp[cnt++] = a[j++];
    for(int k = 0;k < cnt;k++){
        a[l1+k] = temp[k];
    }
}

void mergesort(int a[],int l,int r){
    if(l < r){
        int mid = (l + r) / 2;
        mergesort(a,l,mid);
        mergesort(a,mid+1,r);
        Merge(a,l,mid,mid+1,r);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> a[i];
    }
    mergesort(a,0,n-1);
//    for(int i = 0;i < n;i++){
//        cout << a[i] << " ";
//    }
    cout << ans << endl;
    return 0;
}