結果
問題 | No.1733 Sum of Sorted Subarrays |
ユーザー |
![]() |
提出日時 | 2021-11-05 22:04:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 985 ms / 3,000 ms |
コード長 | 2,429 bytes |
コンパイル時間 | 2,050 ms |
コンパイル使用メモリ | 182,036 KB |
実行使用メモリ | 22,072 KB |
最終ジャッジ日時 | 2024-11-06 12:55:25 |
合計ジャッジ時間 | 18,509 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h>using namespace std;const long long MOD = 998244353;long long modpow(long long a, long long b){long long ans = 1;while (b > 0){if (b % 2 == 1){ans *= a;ans %= MOD;}a *= a;a %= MOD;b /= 2;}return ans;}long long modinv(long long a){return modpow(a, MOD - 2);}struct lazy_segment_tree{int N;vector<long long> ST, lazy;lazy_segment_tree(int N2){N = 1;while (N < N2){N *= 2;}ST = vector<long long>(N * 2 - 1, 1);for (int i = N - 2; i >= 0; i--){ST[i] = ST[i * 2 + 1] + ST[i * 2 + 2];}lazy = vector<long long>(N * 2 - 1, 1);}void eval(int i){if (i < N - 1){lazy[i * 2 + 1] *= lazy[i];lazy[i * 2 + 1] %= MOD;lazy[i * 2 + 2] *= lazy[i];lazy[i * 2 + 2] %= MOD;}ST[i] *= lazy[i];ST[i] %= MOD;lazy[i] = 1;}void range_multiply(int L, int R, int x, int i, int l, int r){eval(i);if (r <= L || R <= l){return;} else if (L <= l && r <= R){lazy[i] = x;eval(i);} else {int m = (l + r) / 2;range_multiply(L, R, x, i * 2 + 1, l, m);range_multiply(L, R, x, i * 2 + 2, m, r);ST[i] = (ST[i * 2 + 1] + ST[i * 2 + 2]) % MOD;}}void range_multiply(int L, int R, int x){range_multiply(L, R, x, 0, 0, N);}long long range_sum(int L, int R, int i, int l, int r){eval(i);if (r <= L || R <= l){return 0;} else if (L <= l && r <= R){return ST[i];} else {int m = (l + r) / 2;return (range_sum(L, R, i * 2 + 1, l, m) + range_sum(L, R, i * 2 + 2, m, r)) % MOD;}}long long range_sum(int L, int R){return range_sum(L, R, 0, 0, N);}};int main(){int N;cin >> N;vector<int> A(N);for (int i = 0; i < N; i++){cin >> A[i];}vector<pair<int, int>> P(N);for (int i = 0; i < N; i++){P[i] = make_pair(A[i], i);}sort(P.begin(), P.end());lazy_segment_tree ST1(N + 1), ST2(N + 1);long long ans = 0;for (int i = 0; i < N; i++){int p = P[i].second;long long L = ST1.range_sum(p + 1, N + 1) * modinv(ST1.range_sum(p, p + 1)) % MOD;long long R = ST2.range_sum(0, p + 1) * modinv(ST2.range_sum(p + 1, p + 2)) % MOD;ans += L * R % MOD * P[i].first % MOD;ST1.range_multiply(p + 1, N + 1, 2);ST2.range_multiply(0, p + 1, 2);}ans %= MOD;cout << ans << endl;}