C++の練習を兼ねて, AtCoder Beginner Contest 256 の 問題F (Cumulative Cumulative Cumulative Sum) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. Binary Indexed Tree の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 個人的には, 解説に記載されている数式を使って, 計算していくロジックが, 非常に面白いと感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 256 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
// 解き直し. // https://atcoder.jp/contests/abc256/editorial/4131 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) const LL MOD = 998244353; LL a[202020]; // Binary Indexed Tree (Fenwick Tree) // https://youtu.be/lyHk98daDJo?t=7960 // -> MOD版 に 改変(2022/06/21). template<typename T> struct BIT{ int n; vector<T> d; BIT(int n = 0) : n(n), d(n + 1) {} void add(int i, T x = 1){ for(i++; i <= n; i += i & -i) d[i] = (d[i] + x) % MOD; } T sum(int i){ T x = 0; for(i++; i; i -= i & -i) x = (x + d[i]) % MOD; return x; } T sum(int l, int r){ return (sum(r - 1) + MOD - sum(l - 1)) % MOD; } }; int main(){ // 1. 入力情報. int N, Q; scanf("%d %d", &N, &Q); rep(i, N) scanf("%lld", &a[i]); // 2. 事前準備. // -> Fenwick Tree を 3個用意する. BIT<LL> ft1(N + 1), ft2(N + 1), ft3(N + 1); repx(i, 1, N + 1){ // i * i * a[i]. ft1.add(i, (LL)i * (LL)i % MOD * a[i - 1] % MOD); // i * a[i]. ft2.add(i, (LL)i * a[i - 1] % MOD); // a[i]. ft3.add(i, a[i - 1]); } // 3. クエリ回答. rep(i, Q){ // 3-1. クエリ入力情報. int f; scanf("%d", &f); // 3-2. クエリ 1. if(f == 1){ int x; LL v; scanf("%d %lld", &x, &v); // a[x](区間[x, x + 1) の 合計)を, v に 置き換える. // i * i * a[i]. LL cur1 = ft1.sum(x, x + 1); ft1.add(x, ((LL)x * (LL)x % MOD * v % MOD + MOD - cur1) % MOD); // i * a[i]. LL cur2 = ft2.sum(x, x + 1); ft2.add(x, ((LL)x * v % MOD + MOD - cur2) % MOD); // a[i]. LL cur3 = ft3.sum(x, x + 1); ft3.add(x, (v + MOD - cur3) % MOD); } // 3-3. クエリ 2. if(f == 2){ int x; scanf("%d", &x); // 区間[1, x + 1) の 合計について, 係数を考慮して, D[x] を 計算. // i * i * a[i]. LL q1 = ft1.sum(1, x + 1); q1 %= MOD; q1 *= 499122177; q1 %= MOD; // i * a[i]. LL q2 = ft2.sum(1, x + 1); q2 %= MOD; q2 *= (LL)(2 * x + 3); q2 %= MOD; q2 *= 499122177; q2 %= MOD; // a[i]. LL q3 = ft3.sum(1, x + 1); q3 %= MOD; q3 *= (LL)(x + 1); q3 %= MOD; q3 *= (LL)(x + 2); q3 %= MOD; q3 *= 499122177; q3 %= MOD; // 出力. printf("%lld\n", (q1 + MOD - q2 + q3) % MOD); } } return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 |
[入力例] 3 3 1 2 3 2 3 1 2 0 2 3 [出力例] 15 9 ※AtCoderテストケースより [入力例] 2 1 998244353 998244353 2 1 [出力例] 0 ※AtCoderテストケースより [入力例] 10 12 96 72 115 31 106 81 57 93 58 110 1 2 19 2 4 1 4 24 1 7 39 2 2 2 3 1 6 22 1 9 88 2 1 1 5 31 1 3 30 2 10 [出力例] 1450 307 748 96 10190 [入力例] 25 30 313 8610 7654 2423 10153 1535 3660 4317 5883 283 7992 11960 1433 4749 7542 2056 9888 11488 675 7366 11897 282 5976 5437 11428 1 6 8971 1 24 3267 1 4 9960 2 21 2 11 1 17 9538 1 12 7337 1 22 8217 2 5 1 7 3611 1 24 6398 2 1 1 8 6281 1 9 9255 2 20 1 25 4288 2 17 2 10 1 5 7164 2 9 1 5 7891 1 4 4727 1 6 10798 1 11 10804 2 6 1 3 3310 1 12 4743 1 1 3322 2 23 2 2 [出力例] 11237518 1812082 176752 313 10000172 6325030 1408711 994451 275096 13561647 18576 [入力例] 50 50 97481596 56913470 20484887 97096478 8115489 111339088 115734595 99553125 85805679 121521835 24333869 36476095 111254902 101662021 68076967 57341299 14384782 7293784 7875941 92252081 95759969 24033082 36749032 79866236 78001189 79367152 77999624 29485924 10388429 64605010 68553065 25993669 56292466 16701153 109941256 11883215 185713 77549992 44723274 60497153 97301159 48552987 114528531 37456326 109030675 59039954 43799330 103816886 78593941 78117787 1 27 95105201 2 7 2 39 2 28 1 2 68118522 1 28 80466466 2 13 1 20 92263222 1 32 88064950 2 28 2 27 1 48 31891698 2 28 2 1 1 22 123044304 1 23 106454807 1 35 110946673 2 16 2 20 1 23 93279411 2 28 1 35 105880627 1 20 96022444 1 41 11586305 2 40 1 4 67251518 1 30 107625160 1 37 1695555 1 39 24388502 1 31 31945776 1 6 53347729 1 31 37833570 2 35 2 1 2 21 2 48 1 32 111919251 2 13 1 37 5026234 1 47 79407780 2 49 1 40 33263713 1 8 57541998 1 28 16290230 2 12 1 17 62593179 2 6 2 50 1 22 82160853 2 25 [出力例] 710128671 621014119 183839522 507893529 477853653 882336553 477853653 97481596 884294293 786360386 444328416 89277185 153609680 97481596 656291952 695401962 771709217 754100544 68869899 760210461 434688344 583595921 |