Codeforces 1167F（计算贡献）

选题失误，这不是很好翻译，但自己看比较容易看懂吧～

## 要点

* 容易想到排序，然后对于每个数：

* 人的惯性思维做法是：$a[i]*(rank1的 rank2的 …)$。然而解法巧妙之处在于直接把所有的加和当成一个系数，然后先假装所有情况系数都是1，接着往上加，树状数组记录着所有之前比它小的数的情况，只有这些小的数也同时存在的区间才会增大它的系数。而且只在乎数量，不关注具体方案。

代码语言：javascript复制

const int maxn = 5e5   5;
const int mod = 1e9   7;
int n, pos[maxn];
ll a[maxn];
ll ans;

struct FenwickTree {
    ll F[maxn], T[maxn];

    void Update1(int x, ll val) {
        for (; x <= n; x  = x&-x)
            F[x]  = val, F[x] %= mod;
    }

    ll Query1(int x) {
        ll res = 0;
        for (; x; x -= x&-x)
            res  = F[x], res %= mod;
        return res;
    }

    void Update2(int x, ll val) {
        for (; x; x -= x&-x)
            T[x]  = val, T[x] %= mod;
    }

    ll Query2(int x) {
        ll res = 0;
        for (; x <= n; x  = x&-x)
            res  = T[x], T[x] %= mod;
        return res;
    }
}bit;

int main() {
    read(n);
    rep(i, 1, n)    read(a[i]), pos[i] = i;
    sort(pos   1, pos   1   n, [](int x, int y) { return a[x] < a[y]; });
    rep(i, 1, n) {
        int p = pos[i];
        //至少系数也得是1吧
        ans  = a[p] * p % mod * (n - p   1) % mod; ans %= mod;
        //然而有比自己小的，把系数挤得大于1
        ans  = a[p] * (bit.Query1(p - 1) * (n - p   1) % mod   bit.Query2(p   1) * p % mod) % mod; ans %= mod;
        bit.Update1(p, p), bit.Update2(p, n - p   1);
    }
    writeln(ans);
    return 0;
}

翻译 排序

0 人点赞