很容易想到分类。
我们可以把 \(1\) 到 \(i-1\) 的球分为两类，一类是权值小于 \(val_i\)，另一类是权值大于 \(val_i\)。
对于第一类，\(sum\) 加上小于 \(val_i\) 的球的个数乘以 \(val_i\)。
对于第二类，\(sum\) 加上所有大于 \(val_i\) 的球的权值。
这显然可以用两个树状数组维护。
最后再乘上总方案数的逆元即可。
复杂度 \(O(n\log n)\)。
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 5, mod = 998244353;
ll n, a[N], c[3][N];
int lbt(int x) {
return x & (-x);
}
void update(int i, ll k, int id) {
for (; i <= 2e5; i += lbt(i)) c[id][i] = (c[id][i] + k) % mod;
}
ll getsum(int i, int id) {
ll res = 0;
for (; i > 0; i -= lbt(i)) res = (res + c[id][i]) % mod;
return res;
}
ll ksm(ll x, ll y) { //求逆元
ll res = 1;
while (y) {
if (y & 1) res = res * x % mod;
y >>= 1;
x = x * x % mod;
}
return res;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
ll sum = 0;
for (ll i = 1; i <= n; ++i) {
sum = (sum + getsum(a[i], 0) * a[i] % mod * 2 % mod) % mod; //小于
sum = (sum + (getsum(2e5, 1) - getsum(a[i], 1) + mod) % mod * 2 % mod) % mod; //大于
sum = (sum + a[i]) % mod; //选了两次都是自己
cout << sum * ksm(i * i % mod, mod - 2) % mod << endl;
update(a[i], 1, 0);
update(a[i], a[i], 1);
}
return 0;
}