<p>Given an integer array <code>nums</code>, return <em>the number of <strong>reverse pairs</strong> in the array</em>.</p>

<p>A <strong>reverse pair</strong> is a pair <code>(i, j)</code> where:</p>

<ul>
	<li><code>0 &lt;= i &lt; j &lt; nums.length</code> and</li>
	<li><code>nums[i] &gt; 2 * nums[j]</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,2,3,1]
<strong>Output:</strong> 2
<strong>Explanation:</strong> The reverse pairs are:
(1, 4) --&gt; nums[1] = 3, nums[4] = 1, 3 &gt; 2 * 1
(3, 4) --&gt; nums[3] = 3, nums[4] = 1, 3 &gt; 2 * 1
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,4,3,5,1]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The reverse pairs are:
(1, 4) --&gt; nums[1] = 4, nums[4] = 1, 4 &gt; 2 * 1
(2, 4) --&gt; nums[2] = 3, nums[4] = 1, 3 &gt; 2 * 1
(3, 4) --&gt; nums[3] = 5, nums[4] = 1, 5 &gt; 2 * 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

#include <bits/stdc++.h>
//// data structure
//#include <atcoder/fenwicktree>
//#include <atcoder/segtree>
//#include <atcoder/lazysegtree>
//#include <atcoder/string>
//// math
//#include <atcoder/math>
//#include <atcoder/convolution>
//#include <atcoder/modint>
//// graph
//#include <atcoder/dsu>
//#include <atcoder/maxflow>
//#include <atcoder/mincostflow>
//#include <atcoder/scc>
//#include <atcoder/twosat>

void fast(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout <<std::fixed << std::setprecision(15);
}
/*
バグが見つからないとき...
入力の仕方でミスっていないか？
怪しい場所をコメントアウトしてコンパイルしてみる
*/
// g++ -ggdb -O2 hoge.cpp -I ~/.pml/ac-library -o zzz
/*
メイン関数内に記述すること
std::ifstream in("testcase/hoge"); std::cin.rdbuf(in.rdbuf());
*/

namespace input{

    template <typename T>
    void read(T& t){
        std::cin >> t;
    }

    template <typename T, typename... Args>
    void read(T& t, Args&... args){
        std::cin >> t;
        read(args...);
    }

    template <typename T>
    void read(std::vector<T>& vec, bool decrement = false){
        for(auto& elem : vec){
            std::cin >> elem;
            if(decrement) elem--;
        }
    }

    template <typename T>
    void read(std::vector<std::vector<T>>& vec, bool decrement = false){
        for(auto& row : vec){
            for(auto& elem : row){
                std::cin >> elem;
                if(decrement) elem--;
            }
        }
    }

    template <typename T, typename... Vectors>
    void read_vectors(int n, std::vector<T>& vec, Vectors&... vecs){
        for(size_t i = 0; i < n; i++){
            read(vec[i], vecs[i]...);
        }
    }

} // namespace input

#define READ(type, ...) \
    type __VA_ARGS__; \
    input::read(__VA_ARGS__)
#define INT(...) READ(int, __VA_ARGS__)
#define LL(...) READ(long long, __VA_ARGS__)
#define DOUBLE(...) READ(double, __VA_ARGS__)
#define LD(...) READ(long double, __VA_ARGS__)
#define STR(...) READ(std::string, __VA_ARGS__)
#define CHAR(...) READ(char, __VA_ARGS__)
#define VI_(type, size, name, ...) \
    std::vector<type> name(size); \
    input::read(name, ##__VA_ARGS__)
#define VI(type, size, name, ...) \
    VI_(type, size, name, ##__VA_ARGS__)
#define VVI_(type, rows, cols, name , ...) \
    std::vector<std::vector<type>> name(rows, std::vector<type>(cols)); \
    input::read(name, ##__VA_ARGS__)
#define VVI(type, rows, cols, name, ...) \
    VVI_(type, rows, cols, name, ##__VA_ARGS__)
#define DECLARE_VECTOR(type, name, size) std::vector<type> name(size)
#define FOR_1(type, size, v1) DECLARE_VECTOR(type, v1, size)
#define FOR_2(type, size, v1, v2) DECLARE_VECTOR(type, v1, size); DECLARE_VECTOR(type, v2, size)
#define FOR_3(type, size, v1, v2, v3) DECLARE_VECTOR(type, v1, size); DECLARE_VECTOR(type, v2, size); DECLARE_VECTOR(type, v3, size)
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define CHOOSE_FOR(type, size, ...) GET_MACRO(__VA_ARGS__, FOR_3, FOR_2, FOR_1)(type, size, __VA_ARGS__)
#define VS(type, size, ...) \
    CHOOSE_FOR(type, size, __VA_ARGS__); \
    input::read_vectors(size, __VA_ARGS__)


namespace output{
    void OUT(){ std::cout << '\n'; }

    template <typename T, typename... Args>
    void OUT(const T& t, const Args&... args){
        std::cout << t;
        if(sizeof...(args)) std::cout << " ";
        OUT(args...);
    }

    template <typename T>
    void OUT(const std::vector<T>& vec, bool space = true){
        for(size_t i = 0; i < vec.size(); i++){
            std::cout << vec[i];
            if(i != vec.size()-1){
                if constexpr (std::is_same<T, std::string>::value){
                    std::cout << '\n';
                } else if(space){
                    std::cout << " ";
                }
            }
        }
        std::cout << '\n';
    }

    template <typename T>
    void OUT(const std::vector<std::vector<T>> &vec, bool space = true){
        for(auto& row : vec){
            OUT(row, space);
        }
    }
}

#define OUT(...) output::OUT(__VA_ARGS__)

namespace debug{
    template <typename T>
    void debug_print(const T& t){
        std::cout << t;
    }

    template <typename T, typename... Args>
    void debug_print(const T& t, const Args&... args){
        std::cout << t << ", ";
        debug_print(args...);
    }
}

#define debug(...) do{ \
    std::cout << #__VA_ARGS__ << " = "; \
    debug::debug_print(__VA_ARGS__); \
    std::cout << '\n'; \
}while(0)

using ll = long long;
using lll = __int128_t;
using ld = long double;
#define newl '\n'
#define INF 1000390039
#define LLINF 1000000039000000039
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LLMAX LONG_LONG_MAX
#define LLMIN LONG_LONG_MIN
#define shift(i) (1LL<<(i))
#define PI acos(-1)
#define tbit(n, k) ((n>>k) & 1) // nの（上から）kビット目
#define bbit(n, k) (n & (1LL<<(k))) // nの（下から）kビット目
#define inr(l, x, r) (l <= x && x < r)
#define einr(l, x, r) (l <= x && x <= r)
#define fore(i, a) for(auto &i : a)
#define rep(i, a, b) for(long long i = (a); i < (b); i++)
#define erep(i, a, b) for(long long i = (a); i <= (b); i++)
#define rrep(i, a, b) for(long long i = (a); i >= (b); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pcnt(x) __builtin_popcount(x)
#define llpcnt(x) __builtin_popcountll(x)
#define v(type, a, name, ...) std::vector<type> name(a, ##__VA_ARGS__)
#define vv(type, a, b, name, ...) std::vector<std::vector<type>> name(a, std::vector<type>(b, ##__VA_ARGS__))
#define vvv(type, a, b, c, name, ...) std::vector<std::vector<std::vector<type>>> name(a, std::vector<std::vector<type>>(b, std::vector<type>(c, ##__VA_ARGS__)))
#define vvvv(type, a, b, c, d, name, ...) std::vector<std::vector<std::vector<std::vector<type>>>> name(a, std::vector<std::vector<std::vector<type>>>(b, std::vector<std::vector<type>>(c, std::vector<type>(d, ##__VA_ARGS__))))
#define vvvvv(type, a, b, c, d, e, name, ...) std::vector<std::vector<std::vector<std::vector<std::vector<type>>>>> name(a, std::vector<std::vector<std::vector<std::vector<type>>>>(b, std::vector<std::vector<std::vector<type>>>(c, std::vector<std::vector<type>>(d, std::vector<type>(e, ##__VA_ARGS__)))))
template <typename T>
int lwb(const std::vector<T>& vec, const T& x){
    return lower_bound(all(vec), x) - vec.begin();
}
template <typename T>
int upb(const std::vector<T>& vec, const T& x){
    return upper_bound(all(vec), x) - vec.begin();
}
template <typename T>
T max(const std::vector<T>& vec){ return *max_element(all(vec)); }
template <typename T>
T min(const std::vector<T>& vec){ return *min_element(all(vec)); }
template <typename T>
T rad(const T& x){ return x * PI/180; }
template <typename T>
using pq = std::priority_queue<T>;
template <typename T>
using pqg = std::priority_queue<T, std::vector<T>, std::greater<T>>;
// 最大値・最小値の更新
template <typename T1, typename T2>
bool chmax(T1 &a, const T2& b){
    if(a < b){ a = b; return 1; }
    else return 0;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2& b){
    if(a > b){ a = b; return 1; }
    else return 0;
}

// @brief 入力演算子を、__int128_t型用にオーバーロード
std::istream& operator>>(std::istream& is, __int128_t& value){
    std::string s;
    is >> s;
    value = 0;
    int start = 0;
    bool is_negative = false;

    if(s[0] == '-'){
        is_negative = true;
        start = 1;
    }

    for(int i = start; i < s.size(); ++i){
        value = 10*value + (s[i]-'0');
    }

    if(is_negative){
        value = -value;
    }

    return is;
}
// @brief 出力演算子を、__int128_t型用にオーバーロード
std::ostream& operator<<(std::ostream& os, __int128_t value){
    if(value == 0) return os << 0;

    static char buffer[128];
    if(value < 0){
        os << '-';
        value = -value;
    }

    int itr = 0;
    while(value > 0){
        buffer[itr++] = value%10 + '0';
        value /= 10;
    }
    std::reverse(buffer, buffer + itr);
    buffer[itr] = 0;

    return os << buffer;
}
// @brief string型の10進非負整数を、__128_t型に変換する
__int128_t parse(const std::string& s){
    __int128_t res = 0;
    for(size_t i = 0; i < s.length(); i++){
        res = 10*res + (s[i]-'0');
    }
    return res;
}

template <typename T>
struct Edge {
    int from, to;
    T cost;
    int id;

    Edge(int to, T cost) : from(-1), to(to), cost(cost), id(-1) {}
    Edge(int from, int to, T cost) : from(from), to(to), cost(cost), id(-1) {}
    Edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost), id(id) {}

    bool operator<(const Edge<T> &rhs) const { return cost < rhs.cost; }

    friend std::ostream &operator<<(std::ostream& os, const Edge& e){
        return os << "(" << e.from << " -> " << e.to << "  weight: " << e.cost << ", id: " << e.id << ")";
    }
};
using Graph = std::vector<std::vector<int>>;
template <typename T>
using Wgraph = std::vector<std::vector<Edge<T>>>;
template <typename T>
using Edges = std::vector<Edge<T>>;

template <typename T, typename F>
// @param ok 解が存在する値
// @param ng 解が存在しない値
// @remark ok > ng の場合は最小値、ok < ng の場合は最大値を返却
T Bsearch(T& ok, T& ng, const F& f){
    while(std::abs(ok-ng) > 1){
        T mid = (ok-ng)/2 + ng;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}
template <typename T, typename F>
T Bsearch_double(T& ok, T& ng, const F& f, int itr = 80){
    while(itr--){
        T mid = (ok+ng)/2;
        //T mid = sqrtl(ok*ng);
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

const int di4[4] = {-1, 0, 1, 0};
const int dj4[4] = {0, 1, 0, -1};
const int di8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dj8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
// @brief 縦・横・斜めのインデックスを生成
std::vector<std::vector<int>> lines(int n){
    std::vector<std::vector<int>> lines;

    for(int i = 0; i < n; i++){
        std::vector<int> line;
        for(int j = 0; j < n; j++){
            line.push_back(i*n + j);
        }
        lines.push_back(line);
    }

    for(int j = 0; j < n; j++){
        std::vector<int> line;
        for(int i = 0; i < n; i++){
            line.push_back(i*n + j);
        }
        lines.push_back(line);
    }

    std::vector<int> diag1;
    for(int i = 0; i < n; i++){
        diag1.push_back(i*n + i);
    }
    lines.push_back(diag1);

    std::vector<int> diag2;
    for(int i = 0; i < n; i++){
        diag2.push_back(i*n + (n-i-1));
    }
    lines.push_back(diag2);

    return lines;
}

bool OutOfGrid(const int& i, const int& j, const int& h, const int& w){
    if(i < 0 || j < 0 || i >= h || j >= w) return true;
    return false;
}

namespace math{

    // @brief 繰り返し二乗法を利用した、x^nの求値
    ll pow(ll x, ll n){
        ll res = 1;

        while(n){
            if(n & 1) res *= x;
            x *= x;
            n >>= 1;
        }

        return res;
    }

    // @brief x/mのfloor（x/m以下の最大の整数）を求める
    ll floor(const ll& x, const ll& m){
        ll r = (x%m + m) % m; // xをmで割った余り
        return (x-r)/m;
    }

    // @brief x/mのceil（x/m以上の最小の整数）を求める
    ll ceil(const ll& x, const ll& m){
        return floor(x+m-1, m); // x/m + (m-1)/m
    }

} // namespace math

// @brief prefix_sum[i][j] := [0, i)×[0, j) での二次元配列の総和
// @brief f(i, j) := a[i][j]の値
// @rem 貰う遷移で埋めていく
template <typename T>
std::vector<std::vector<T>> prefix_sum(const int& h, const int& w, const std::function<T(int, int)>& f) {
    std::vector<std::vector<T>> sum(h+1, std::vector<T>(w+1, T()));
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            sum[i+1][j+1] = f(i, j) + sum[i][j+1] + sum[i+1][j] - sum[i][j];
        }
    }
    return sum;
}

// @brief suffix_sum[i][j] := [0, i)×[0, j) での二次元配列の総和
// @brief f(i, j) := a[i][j]の値
// @rem 貰う遷移で埋めていく
template <typename T>
std::vector<std::vector<T>> suffix_sum(const int& h, const int& w, const std::function<T(int, int)>& f) {
    std::vector<std::vector<T>> sum(h+1, std::vector<T>(w+1, T()));
    for(int i = h-1; i >= 0; i--){
        for(int j = w-1; j >= 0; j--){
            sum[i][j] = f(i, j) + sum[i+1][j] + sum[i][j+1] - sum[i+1][j+1];
        }
    }
    return sum;
}

using namespace std;

namespace atcoder {

template <class T> struct fenwick_tree {

  public:
    fenwick_tree() : _n(0) {}
    explicit fenwick_tree(int n) : _n(n), data(n) {}

    void add(int p, T x) {
        assert(0 <= p && p < _n);
        p++;
        while (p <= _n) {
            data[p - 1] += x;
            p += p & -p;
        }
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        return sum(r) - sum(l);
    }

private:
    int _n;
    std::vector<T> data;

    T sum(int r) {
        T s = 0;
        while (r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }
};

}  // namespace atcoder

class Solution {
public:
    void update(vector<long long> &tree, long long idx, long long del, long long n) {
        for(long long i = idx+1; i<=n; i+=(i&(-i))) {
            tree[i]+=del;
        }
    }
    long long query(vector<long long> &tree, long long idx) {
        long long res = 0;
        for(long long i = idx+1; i>0; i-=(i&(-i))) {
            res+=tree[i];
        }
        return res;
    }
    int reversePairs(vector<int>& nums) {
        long long n = nums.size();
        vector<pair<long long,long long>> v;
        for(long long i = 0; i<n; i++) {
            v.push_back({nums[i],i});
        }
        sort(v.begin(), v.end());
        map<long long,vector<long long>> queries;
        for(long long i = 0; i<n; i++) {
            long long x = 2*(v[i].first);
            long long l = 0;
            long long r = n;
            while(l<r) {
                long long mid = (l+r)/2;
                if (v[mid].first > x) r = mid;
                else l = mid+1;
            }
            queries[r].push_back(v[i].second-1);
        }
        long long ans = 0;
        //vector<long long> tree(n+1, 0);
        atcoder::fenwick_tree<ll> fw(n+1);
        for(long long i = n-1; i>=0; i--) {
            //update(tree, v[i].second, 1, n);
            fw.add(v[i].second, 1);
            for (auto x : queries[i]) {
                //long long res = query(tree, x);
                long long res = fw.sum(0, x+1);
                ans+=res;
            }
        }
        return ans;
    }
};

122258