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

对于一个逆序对 i j 来说，其在子序列中出现的次数是固定的，是 2^(n-2)，因为对于 n 个数而言，i 和 j 必须出现在逆序对中，而其他数都可以出现或者不出现，所以每个逆序对都会出现 2^(n-2) 次，答案就是逆序对数量乘 2^(n-2)

而求逆序对数量很简单了，实现方法很多，这里给一个树状数组实现的方法

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int __t = 1, n, a[N], s[N], f[N] = {1, 1, 1};
void update(int x, int y) {
    for (; x <= 1e5; x += x & -x)
        s[x] = (s[x] + y) % mod;
}
int query(int x) {
    int res = 0;
    for (; x; x -= x & -x)
        res = (res + s[x]) % mod;
    return res;
}
void solve() {
    for (int i = 3; i < N; ++i)
        f[i] = f[i - 1] * 2 % mod;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        ans = (ans + (query(1e5) - query(a[i]) + mod) % mod) % mod;
        update(a[i], 1);
    }
    cout << ans * f[n] % mod << '\n';
}
int32_t main() {
#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    // cin >> __t;
    while (__t--)
        solve();
    return 0;
}