solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

template <typename T>
struct Fenwick {
#define lowbit(x) x & -x
    const int n;
    vector<T> a;
    // [1, n]
    Fenwick(int n) : n(n), a(n + 1) {}
    void add(int x, T v) {
        while (x > 0) {
            a[x] += v;
            x -= lowbit(x);
        }
    }

    // [1, x]
    T query(int x) {
        T res = 0;
        while (x <= n) {
            res += a[x];
            x += lowbit(x);
        }
        return res;
    }
};

class Solution {
   public:
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        vector<int> x(n);
        for (int i = 0; i < n; i++) {
            x[i] = nums[i];
        }
        sort(x.begin(), x.end());
        int x_num = unique(x.begin(), x.end()) - x.begin();
        x.resize(x_num);

        Fenwick<int> fen(x_num);
        int ans = 0;
        debug(x);

        for (int i = 0; i < n; i++) {
            int val = nums[i];
            long long big = 1LL * val * 2;
            int idx = upper_bound(x.begin(), x.end(), big) - x.begin();
            if (idx != x.size()) {
                ans += fen.query(idx + 1);
                debug(i, ans);
            }
            idx = lower_bound(x.begin(), x.end(), val) - x.begin();
            debug(idx);
            fen.add(idx + 1, 1);
        }
        return ans;
    }
};