提出 #36245481

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
typedef long long ll;
using namespace std;
const int maxn = 2e5 + 5;
const int mod = 998244353;
void amod(int &x, int y) {
	x = x + y >= mod ? x + y - mod : x + y;
}
int inc(int x, int y) {
	return x + y >= mod ? x + y - mod : x + y;
}
int ksm(int x, int y = mod - 2) {
	int res = 1;
	for(; y > 0; y >>= 1, x = 1ll * x * x % mod) {
		if(y & 1) {
			res = 1ll * res * x % mod;
		}
	}
	return res;
}
int n, a[maxn];
pair<int, int> lsh[maxn];
#define lc (x << 1)
#define rc (x << 1 | 1)
#define mid ((l + r) >> 1)
int sum[maxn * 4], len[maxn * 4], add[maxn * 4], cnt[maxn * 4];
void push_up(int x) {
	len[x] = inc(len[lc], len[rc]);
	sum[x] = inc(sum[lc], sum[rc]);
	cnt[x] = cnt[lc] + cnt[rc];
}
void push_add(int x, int v) {
	amod(sum[x], 1ll * v * len[x] % mod);
	amod(add[x], v);
}
void push_down(int x) {
	if(add[x]) {
		push_add(lc, add[x]);
		push_add(rc, add[x]);
		add[x] = 0;
	}
}
void modify(int x, int l, int r, int p, int v) {
	if(l == r) {
		len[x] = v;
		cnt[x] = 1;
		return;
	}
	push_down(x);
	mid >= p ? modify(lc, l, mid, p, v) : modify(rc, mid + 1, r, p, v);
	push_up(x);
}
void update(int x, int l, int r, int L, int R, int v) {
	if(l >= L && r <= R) {
		push_add(x, v);
		return;
	}
	push_down(x);
	if(mid >= L) {
		update(lc, l, mid, L, R, v);
	}
	if(mid < R) {
		update(rc, mid + 1, r, L, R, v);
	}
	push_up(x);
}
int query(int x, int l, int r, int L, int R) {
	if(L > R) {
		return 0;
	}
	if(l >= L && r <= R) {
		return cnt[x];
	}
	push_down(x);
	int res = 0;
	if(mid >= L) {
		res += query(lc, l, mid, L, R);
	}
	if(mid < R) {
		res += query(rc, mid + 1, r, L, R);
	}
	return res;
}
#undef lc
#undef rc
#undef mid
int main() {
#ifdef DEBUG
	freopen("1.in", "r", stdin);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		lsh[i] = mp(a[i], i);
	}
	sort(lsh + 1, lsh + 1 + n);
	int s = 0;
	for(int i = 1; i <= n; i++) {
		int p = lower_bound(lsh + 1, lsh + 1 + n, mp(a[i], i)) - lsh;
		if(p + 1 <= n) {
			update(1, 1, n, p + 1, n, 1);
		}
		amod(s, a[i]);
		modify(1, 1, n, p, a[i]);
		update(1, 1, n, p, p, query(1, 1, n, 1, p - 1));
		int ans = inc(s, inc(sum[1], sum[1]));
		ans = 1ll * ans * ksm(1ll * i * i % mod) % mod;
		cout << ans << '\n';
	}
	return 0;
}

提出情報

ジャッジ結果