题解 | #小红的子序列逆序对#（线段树+快速幂）

#include "bits/stdc++.h"

using namespace std;
#define int long long
vector<int> tr, lz, a;
#define ls (now<<1)
#define rs (now<<1|1)
#define mid (l+r>>1)
const int MOD = 1e9 + 7;

long long qpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

void pushup(int now) { tr[now] = tr[ls] + tr[rs]; }

void pushdown(int now, int l, int r) {
    tr[ls] += lz[now] * (mid - l + 1), tr[rs] += lz[now] * (r - mid);
    lz[ls] += lz[now], lz[rs] += lz[now];
    lz[now] = 0;
}

void build(int now, int l, int r) {//建树
    if (l == r) {
        tr[now] = a[l];
        return;
    }
    build(ls, l, mid), build(rs, mid + 1, r);
    pushup(now);
}

void modify(int now, int l, int r, int ml, int mr, int k) {//修改
    if (l == ml && r == mr) {
        tr[now] += (r - l + 1) * k, lz[now] += k;
        return;
    }
    pushdown(now, l, r);
    if (mr <= mid) modify(ls, l, mid, ml, mr, k);
    else if (ml > mid) modify(rs, mid + 1, r, ml, mr, k);
    else modify(ls, l, mid, ml, mid, k), modify(rs, mid + 1, r, mid + 1, mr, k);
    pushup(now);
}

int query(int now, int l, int r, int ml, int mr) {//查询
    if (l == ml && r == mr) return tr[now];
    pushdown(now, l, r);
    if (mr <= mid) return query(ls, l, mid, ml, mr);
    else if (ml > mid) return query(rs, mid + 1, r, ml, mr);
    else return query(ls, l, mid, ml, mid) + query(rs, mid + 1, r, mid + 1, mr);
}

void slu() {
    int n;
    cin >> n;
    int cnt = 0;
    int N = 1e5 + 7;
    a.resize(N << 2, 0);
    lz.resize(N << 2, 0);
    tr.resize(N << 2, 0);
    vector<int> b(n + 1, 0);
    unordered_map<int, int> m;
    for (int i = 1; i <= n; i++)cin >> b[i];
    for (int i = n; i >= 1; i--) {
        int t = b[i];
        m[t]++;
        modify(1, 1, 1e5, t, t, 1);
        cnt += query(1, 1, 1e5, 1, t) - m[t];
    }
    cnt = (qpow(2, n - 2, MOD) * (cnt % MOD)) % MOD;
    cout << cnt;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
//    cin >> T;
    T = 1;
    while (T--)slu();

}