题目描述

blablabla

样例

#include<stdio.h>
#include<iostream>
typedef long long LL;

using namespace std;    
const int N = 100010;
int q[N], temp[N];
LL merge(int q[], int l, int r){
    if(l >= r) return 0;
    int mid = l + r >> 1;
    LL res = merge(q, l, mid) + merge(q, mid+1, r);
    int i = l, j = mid +1, k = 0;
    while(i <= mid && j <= r){
//      绝对大小  
        if(q[i] <= q[j]) temp[k++] = q[i++];
        else {res += mid - i + 1; temp[k++] = q[j++];}
    }
//  若左半边还剩下，那么右半边无元素，所以实际上是没有左右半边逆序对的 
    while(i <= mid) {temp[k++] = q[i++];}
//  若右半边剩下，说明左边都比右边大了，逻辑上没有逆序对 
    while(j <= r) temp[k++] = q[j++];
    for(int i = l, j = 0; i <= r; i++, j++) q[i] = temp[j];
    return res;
}
int main(){
    int n; cin >> n;
    for(int i = 0; i < n; i++){
        scanf("%d",&q[i]);
    }
//  for(int i = 0; i < n; i ++){
//      cout << q[i] << " ";
//  }
    cout << merge(q, 0, n - 1);
    return 0;
} 

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla