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;

}

#翻译#排序