题解 [ABC276F] Double Chance

很容易想到分类。

我们可以把 \(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;
}