计算逆序对问题 OJ OJ运行超时：Time Limit Exceeded

问题遇到的现象

OJ运行超时： Time Limit Exceeded

条件

内存限制：64 MiB
时间限制：1000 ms
标准输入输出
题目类型：传统
评测方式：文本比较

题目

题目描述
设A[1..n]是一个包含N个数的数组。如果在i〈 j的情况下，有A[i] 〉a[j]，则(i,j)就称为A中的一个逆序对。
使用归并排序可以用O(nlogn)的时间解决统计逆序对个数的问题。
输入格式
第1行：1个整数N表示排序元素的个数。(1≤N≤100000) 第2行：N个用空格分开的整数，每个数在小于100000
输出格式
1行：仅一个数，即序列中包含的逆序对的个数
样例
样例输入
3
1 3 2
样例输出
1

问题相关代码，请勿粘贴截图

#include <iostream>
using namespace std;
int main()
{
    long long NUM,l = 0,O,P = 0;
    cin >> O;
    int num[O];
    for(int i = 0;i < O;i++)
    {
        cin >> NUM;
        num[i] = NUM;
        for(int v = i - 1;v > -1;v--)
        {
            if(num[i] < num[v])
                P++;
        }
    }
    cout << P;
}

```

运行结果及报错内容

报错0：Exited with return code 0
结果正常
运行超过OJ时间限制

我的解答思路和尝试过的方法

1)定义数组存储集合
2)比对集合中符合条件元素的大小
3)输出

我想要达到的结果

OJ Accept

解决一个问题的第一步是定义清楚问题。

首先我们给出逆序对的定义：
对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对。
重要的地方在于，一个元素可以不只是在一个逆序对中存在。如果 k > j > i 且 a[i] > a[j] > a[k]，那么这里
有两个含 a[i] 的逆序对，分别是 (a[i], a[j]) 和 (a[i], a[k]), a[i]是可以使用多次的。

那么第二步是分析问题，这里我们可以使用分治法解决问题。

我们将序列从中间分开，将逆序对分成三类：

两个元素都在左边；
两个元素都在右边；
两个元素一个在左一个在右；
因此这就是我们算法的大致框架：

计算逆序对的数量（序列）：

递归算左边的；
递归算右边的；
算一个左一个右的；
把他们加到到一起。

这个时候我们注意到一个很重要的性质，左右半边的元素在各自任意调换顺序，是不影响第三步计数的，因此我们可以数完就给它排序。这么做的好处在于，如果序列是有序的，会让第三步计数很容易。
如果无序暴力数的话这一步是O(n^2)的。

比如序列是这样的

4 5 6 | 1 2 3
当你发现 4 比 3 大的时候，也就是说右边最大的元素都小于左边最小的元素，那么左边剩下的5和6都必然比右边的所有元素大，因此就可以不用数5和6的情形了，直接分别加上右半边的元素个数就可以了，这一步就降低到了
O(n), 我们知道递归式 T(n) = 2T(n/2)+O(n) = O(nlogn)的，所以排序的成本是可以接受的，并且这一问题下，
可以很自然地使用归并排序。

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], tmp[N];
LL merge_sort(int q[], int l, int r){
    if (l >= r) return 0;
    int mid = l + r >> 1;
    LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else{
            res += mid - i + 1;
            tmp[k ++ ] = q[j ++ ];
        }
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
    return res;
}
int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    cout << merge_sort(a, 0, n - 1) << endl;
    return 0;
}

def merge_sort(s,l,r):
    if l >= r: return 0
    mid = l + r >> 1
    res = merge_sort(s,l,mid) + merge_sort(s,mid + 1,r)
    i = l
    j = mid + 1
    tmp = []
    while(i <= mid and j <= r):
        if(s[i] <= s[j]):
            tmp.append(s[i])
            i += 1
        else:
            res += (mid - i + 1)
            tmp.append(s[j])
            j += 1
            pass
        pass
    while(i <= mid):
        tmp.append(s[i])
        i += 1
        pass
    while(j <= r):
        tmp.append(s[j])
        j += 1
        pass
    s[l:r + 1] = tmp
    return res
n = eval(input())
s = list(map(int,input().split()))
print(merge_sort(s, 0, n - 1))

递归归并排序求逆序对，应该能过


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100005];
ll b[100005];
ll sum = 0;

void merge(ll left, ll mid, ll right){
    ll left_pos = left;
    ll right_pos = mid + 1;
    ll new_pos = left;
    while(left_pos <= mid && right_pos <= right){
        if(a[left_pos] <= a[right_pos])b[new_pos++] = a[left_pos++];
        else{
            b[new_pos++] = a[right_pos++];
            sum += (mid - left_pos + 1);
        } 
    }
    while(left_pos <= mid)b[new_pos++] = a[left_pos++];
    while(right_pos <= right)b[new_pos++] = a[right_pos++];
    
    while(left<=right){
        a[left] = b[left];
        left++;
    }
}

void msort(ll left, ll right){
    if(left < right){
        ll mid = (left + right) / 2;
        msort(left, mid);
        msort(mid+1, right);
        merge(left, mid, right);
    } 
}

int main(){
    ll n;
    cin>>n;
    for(ll i=0; i<n; i++)scanf("%d", &a[i]);
    msort(0, n-1);
//     for(int i=0; i<n; i++)printf("%d ", a[i]);
cout<<sum;
    return 0;
}