题解 | #小红的子序列逆序对#

需要树状数组，线段树会被卡

#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <numeric>
#include <ctime>
#include <string>
#include <bitset>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;
const ll N = 1e5 + 5, mod = 1e9 + 7, inf = 2e18;


ll n, a[N];
ll bit[N]; // 树状数组

// 树状数组的基本操作
void update(int idx, ll val) {
    while (idx < N) {
        bit[idx] += val;
        idx += idx & -idx; // 前往下一节点
    }
}

ll query(int idx) {
    ll sum = 0;
    while (idx > 0) {
        sum += bit[idx];
        idx -= idx & -idx; // 回溯至父节点
    }
    return sum;
}

// 计算快速幂
ll pqmi(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans *= a;
            ans %= mod;
        }
        b >>= 1;
        a *= a;
        a %= mod;
    }
    return ans;
}

void solve() {
    cin >> n;
    vector<ll> vals;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        vals.push_back(a[i]);
    }

    // 离散化处理
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    ll ans = 0;

    for (int i = n; i >= 1; i--) {
        // 获取当前值的离散化索引
        int idx = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1;

        // 查询比当前值小的数量
        ans += query(idx - 1);
        ans %= mod;

        // 更新当前值至树状数组
        update(idx, 1);
    }

    // 最终结果乘以快速幂
    ans *= pqmi(2, n - 2);
    ans %= mod;

    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}