题目描述

blablabla

样例

#include <iostream>

using namespace std;

const int N = 100010;
int n, num[N], temp[N];

typedef long long LL;

LL mergeCount(int q[], int start, int end){
    if (start >= end)return 0;

    int mid = (start + end) >> 1;

    // 这里是逆序对两个数都在左区间和右区间的对数
    LL res = mergeCount(q, start, mid)+mergeCount(q, mid+1, end);

    int i = start, j = mid+1, k = start;
    while (i <= mid && j <= end){
        if (q[i] <= q[j])temp[k++] = num[i++];
        else {
            // 每一个j指针+1的时候，证明i指针到mid+1位置的数都比j指针指向的数大
            res += mid - i + 1;
            temp[k++] = num[j++];
        }
    }

    while(i<=mid){
        temp[k++]=num[i++];
    }
    while(j<=end){
        temp[k++]=num[j++];
    }

    for(int s = start; s<=end; s++){
        num[s] = temp[s];
    }

    return res;
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i ++)scanf("%d", &num[i]);

    LL res = mergeCount(num, 0, n - 1);

    cout << res;


}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla