lessons/参考实现/08-高级线段树与树状数组/AtCoder-agc023_e.cpp

#include <bits/stdc++.h>
using namespace std;

constexpr long long MOD = 1'000'000'007LL;

long long mod_power(long long base, long long exponent) {
    long long result = 1;
    while (exponent > 0) {
        if (exponent & 1) result = result * base % MOD;
        base = base * base % MOD;
        exponent >>= 1;
    }
    return result;
}

struct Fenwick {
    int n;
    vector<long long> tree;
    explicit Fenwick(int n) : n(n), tree(n + 1, 0) {}
    void add(int index, long long value) {
        value %= MOD;
        for (; index <= n; index += index & -index) {
            tree[index] += value;
            if (tree[index] >= MOD) tree[index] -= MOD;
        }
    }
    long long sum(int index) const {
        long long result = 0;
        for (; index > 0; index -= index & -index) result = (result + tree[index]) % MOD;
        return result;
    }
    long long range_sum(int left, int right) const {
        if (left > right) return 0;
        return (sum(right) - sum(left - 1) + MOD) % MOD;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n), frequency(n + 1, 0);
    for (int &x : a) {
        cin >> x;
        ++frequency[x];
    }
    vector<int> at_least(n + 2, 0), choices(n + 1, 0);
    for (int value = n; value >= 1; --value) {
        at_least[value] = at_least[value + 1] + frequency[value];
        choices[value] = at_least[value] - (n - value);
        if (choices[value] <= 0) {
            cout << 0 << '\n';
            return 0;
        }
    }

    long long permutations = 1;
    vector<long long> prefix(n + 1, 1), inverse_prefix(n + 1, 1);
    vector<int> zero_count(n + 1, 0);
    for (int value = 1; value <= n; ++value) {
        permutations = permutations * choices[value] % MOD;
        prefix[value] = prefix[value - 1];
        zero_count[value] = zero_count[value - 1];
        if (choices[value] == 1) {
            ++zero_count[value];
        } else {
            prefix[value] = prefix[value] * (choices[value] - 1) % MOD;
            prefix[value] = prefix[value] * mod_power(choices[value], MOD - 2) % MOD;
        }
        inverse_prefix[value] = mod_power(prefix[value], MOD - 2);
    }

    vector<int> group_left(n + 1), group_right(n + 1);
    for (int left = 1; left <= n;) {
        int right = left;
        while (right + 1 <= n && zero_count[right + 1] == zero_count[left]) ++right;
        for (int value = left; value <= right; ++value) {
            group_left[value] = left;
            group_right[value] = right;
        }
        left = right + 1;
    }

    Fenwick counts(n), sum_prefix(n), sum_inverse(n);
    const long long inverse_two = (MOD + 1) / 2;
    long long normalized = 0;
    long long inversions_of_a = 0;
    int inserted = 0;
    for (int value : a) {
        long long greater = inserted - counts.sum(value);
        inversions_of_a = (inversions_of_a + greater) % MOD;

        long long lower_inverse = sum_inverse.range_sum(group_left[value], value);
        normalized = (normalized + prefix[value] * lower_inverse) % MOD;

        long long higher_prefix = sum_prefix.range_sum(value + 1, group_right[value]);
        normalized = (normalized - inverse_prefix[value] * higher_prefix) % MOD;
        if (normalized < 0) normalized += MOD;

        counts.add(value, 1);
        sum_prefix.add(value, prefix[value]);
        sum_inverse.add(value, inverse_prefix[value]);
        ++inserted;
    }

    long long answer = permutations * inversions_of_a % MOD;
    answer = (answer + permutations * inverse_two % MOD * normalized) % MOD;
    cout << answer << '\n';
    return 0;
}