数组逆序数计算：基于ordered_multiset的代码未AC求问题排查

问题描述 #

给定由n个不同正整数组成的数组A[0...n-1]，若i<j且A[i]>A[j]，则(i,j)称为A的一个逆序对，需计算数组的逆序数。

输入输出规则 #

• 输入：第一行是测试用例数t，每个测试用例先输入n（n≤200000），随后n+1行，前n行是数组元素（元素≤10^7），第n+1行为空行。
• 输出：每个测试用例输出一行，为数组的逆序数。

样例 #

输入 #

2
3
3
1
2
5
2
3
8
6
1

输出 #

2
5

代码实现 #

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
struct ordered_multiset {
    int len = 0;
    const int ADD = 1000010;
    const int MAXVAL = 1000000010;
    unordered_map<int, int> mp;
    tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> T;
    inline void insert(int x){
        len++, x += MAXVAL;
        int c = mp[x]++;
        T.insert((x * ADD) + c); }
    inline int upper_bound(int x){
        x += MAXVAL;
        int c = mp[x];
        return (T.order_of_key((x*ADD)+c)); }
    inline void clear()
    {
        len = 0;
        T.clear();
        mp.clear();
    }
    inline int size() { return len; }
};
int main() {
    ios_base::sync_with_stdio(false);
    int tests;
    cin >> tests;
    while (tests--)
    {
        int n;
        cin >> n;
        ordered_multiset Messi;
        long long nr = 0;
        for (int i = 1; i <= n; i++)
        {
            int x;
            cin >> x;
            Messi.insert(x);
            nr += Messi.size() - Messi.upper_bound(x);
        }
        Messi.clear();
        cout << nr << '\n';
    }
    return 0;
}

疑问 #

已知存在基于MergeSort的高效解法，本人尝试使用ordered_multiset的方案实现，代码可通过样例但提交未被AC，希望得到帮助排查代码问题。

内容的提问来源于stack exchange，提问作者bibozisbibogel