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

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // Write your code here
    let params = [];
    while ((line = await readline())) {
        let tokens = line.split(" ");
        // let a = parseInt(tokens[0]);
        // let b = parseInt(tokens[1]);
        // console.log(a + b);
        params.push(tokens);
    }
    // console.log(params)
    let n = parseInt(params[0][0]);
    let arr = params[1].map((v) => parseInt(v));
    // console.log(n,arr)
    let MOD = BigInt(Math.pow(10, 9) + 7);
    // console.log(MOD)
    // 树状数组求子序列
    class Fenwick {
        constructor(size) {
            this.size = size;
            this.tree = new Array(size + 1).fill(0);
        }
        update(i, delta) {
            while (i <= this.size) {
                this.tree[i] += delta;
                i += i & -i;
            }
        }
        query(i) {
            let ans = 0;
            while (i > 0) {
                ans += this.tree[i];
                i -= i & -i;
            }
            return ans;
        }
    }
    // 去重和离散化
    let sortedArr = [...new Set(arr)].sort((a, b) => a - b);
    let rankMap = new Map();
    sortedArr.forEach((v, index) => {
        rankMap.set(v, index + 1);
    });
    let sum = 0;
    let fenwick = new Fenwick(sortedArr.length);
    for (let i = arr.length - 1; i >= 0; i--) {
        let rank = rankMap.get(arr[i]);
        sum += fenwick.query(rank - 1);
        fenwick.update(rank, 1);
    }
    sum = BigInt(sum)
    let power = BigInt(1);
    // 计算2^(n-2) mod MOD（快速幂算法）
    let exponent = BigInt(n - 2);
    let base = 2n;
    while (exponent > 0) {
        if (exponent & 1n) {
            power = (power * base) % MOD;
        }
        base = base * base;
        exponent >>=1n
    }
    console.log(Number(((sum % MOD) * power) % MOD));
})();