题解 | #数组中的逆序对#

#define ll long long
#define lowbit(x) x&(-x)
#define mod 1000000007
vector<int>a, t, d;
bool cmp(int x, int y) {
    return a[x] == a[y] ? x > y : a[x] > a[y];
}
int n;
void add(int x) {
    while (x <= n) {
        t[x]++;
        x += lowbit(x);
    }
}
int ask(int x) {
    int ans = 0;
    while (x >= 1) {
        ans += t[x];
        x -= lowbit(x);
    }
    return ans;
}
class Solution {
  public:
    int InversePairs(vector<int> data) {
        n = data.size();
        a = vector<int>(n + 1), t = vector<int>(n + 1), d = vector<int>(n + 1);
        for (int i = 1; i <= n; i++)a[i] = data[i - 1], d[i] = i;
        sort(d.begin() + 1, d.end(), cmp);
        long long res = 0;
        for (int i = 1; i <= n; i++) {
            add(d[i]);
            res = (res + ask(d[i]) - 1) % mod;
        }
        return res % mod;
    }
};