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

#include <stdio.h>
#define mod 1000000007
#define N 100100
// 定义全局数组用于存储原始数组元素以及树状数组
int a[N];
long long tr[N];

// 向树状数组中添加值的函数，用于更新树状数组
void add(int now, int val) {
    for (int i = now; i < N; i += i & -i) {
        tr[i] += val;
    }
}

// 查询树状数组前缀和的函数，用于获取小于等于某个值的元素个数
long long query(int now) {
    long long res = 0;
    for (int i = now; i > 0; i -= i & -i) {
        res += tr[i];
    }
    return res;
}

int main() {
    long long res = 0, cnt = 1;
    int n, i;
    scanf("%d", &n);
    for (i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for (i = 1; i <= n; ++i) {
        add(a[i], 1);
        res += i - query(a[i]);
    }
    for (i = 2; i < n; ++i) {
        cnt = (cnt * 2) % mod;
    }
    printf("%lld\n", (res % mod * cnt % mod) % mod);
    return 0;
}