Submission #36249590

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

namespace acah
{
	constexpr int maxn = 2e5 + 7;
	constexpr int p = 998244353;
	constexpr int H = 2e5;
	
	int N, A[maxn], cc[maxn], cs[maxn], s, S;
	
	inline void add(int &a, int b) {a += b, a -= (a >= p ? p : 0);}
	
	inline int lbt(int x) {return x & (-x);}
	inline void upd(int p, int x) {for(; p <= H; p += lbt(p)) ++cc[p], add(cs[p], x);}
	inline int qryc(int p) {int s = 0; for(; p; p -= lbt(p)) s += cc[p]; return s;}
	inline int qrys(int p) {int s = 0; for(; p; p -= lbt(p)) add(s, cs[p]); return s;}
	
	inline int inv(int a)
	{
		for(int t = a, x = p - 3; x; t = 1ll * t * t % p, x >>= 1)
			if(x & 1) a = 1ll * a * t % p;
		return a;
	}
	
	int work()
	{
		ios::sync_with_stdio(false), cin.tie(nullptr);
		
		cin >> N; for(int i = 1; i <= N; i++) cin >> A[i];
		for(int i = 1; i <= N; i++) {
			add(S, A[i]), upd(A[i], A[i]);
			add(s, 2ll * A[i] * (qryc(A[i]) - 1) % p);
			add(s, A[i]);
			add(s, 2ll * (S + p - qrys(A[i])) % p);
			cout << 1ll * s * inv(1ll * i * i % p) % p << '\n';
		}
		
		return 0;
	}
}

int main() {return acah::work();}

Submission Info

Judge Result