C++の練習を兼ねて, AtCoder Beginner Contest 221 の 問題E (LEQ) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. Binary Indexed Tree の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 221 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題E／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 |
// 解き直し. // https://atcoder.jp/contests/abc221/editorial/2718 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<LL, int>; using vp = vector<P>; #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--) #define a first #define b second #define pb push_back const LL MOD = 998244353; LL mPow2Mod[303030], pPow2Mod[303030]; // Binary Indexed Tree (Fenwick Tree) // https://youtu.be/lyHk98daDJo?t=7960 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] += x; } T sum(int i){ T x = 0; for(i++; i; i -= i & -i) x += d[i]; return x; } T sum(int l, int r){ return sum(r - 1) - sum(l - 1); } }; int main(){ // 1. 入力情報. int N; scanf("%d", &N); map<P, int> m; vp v; rep(i, N){ LL a; scanf("%lld", &a); P p = {a, i + 1}; m[p] = 0; v.pb(p); } // 2. 2 の 冪乗(正／負). pPow2Mod[0] = mPow2Mod[0] = 1; rep(i, N + 1){ pPow2Mod[i + 1] = (2 * pPow2Mod[i]) % MOD; // 正. mPow2Mod[i + 1] = (499122177 * mPow2Mod[i]) % MOD; // 負. } // 3. 座標圧縮. int idx = 0; for(auto &p : m) p.b = ++idx; // 4. 集計(解説通り). // ex. // 5 // 2 1 1 3 2 // -> {整数列 A の 要素(座標圧縮), BIT の 加算位置} // = {{2, 3}, {1, 1}, {1, 2}, {3, 5}, {2, 4}} のように 番号付けしておく. // // B[1] = 0 (BIT の 位置 3 に, 1 / 2 を 加算, 位置 2 までの総和) // B[2] = 0 (BIT の 位置 1 に, 1 / 4 を 加算, 位置 0 までの総和) // B[3] = 1 / 4 (BIT の 位置 2 に, 1 / 8 を 加算, 位置 1 までの総和) // B[4] = 1 / 4 + 1 / 8 + 1 / 2 (BIT の 位置 5 に, 1 / 16 を 加算, 位置 4 までの総和) // B[5] = 1 / 4 + 1 / 8 + 1 / 2 (BIT の 位置 4 に, 1 / 32 を 加算, 位置 3 までの総和) // -> よって, これらを集計すると, 22 が 計算結果と分かる. // ans = B[1] * 1 + B[2] * 2 + B[3] * 4 + B[4] * 8 + B[5] * 16 // = 0 + 0 + 1 + 7 + 14 // = 22 BIT<LL> ft(N + 1); LL ans = 0; rep(j, N){ // 整数列 A の 要素 を 取得. P p = v[j]; // BIT の 加算位置. int i = m[p]; // 上記の場所に, 2 の 冪乗(負) を 加算. ft.add(i, mPow2Mod[j + 1]); // 区間[1, i) の 合計は？ LL t = ft.sum(1, i) % MOD; // 計算結果に, 2 の 冪乗(正) を 乗算. t *= pPow2Mod[j]; t %= MOD; // 集計. ans += t; ans %= MOD; } // 5. 出力. printf("%lld\n", ans); 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 |
[入力例] 3 1 2 1 [出力例] 3 ※AtCoderテストケースより [入力例] 3 1 2 2 [出力例] 4 ※AtCoderテストケースより [入力例] 3 3 2 1 [出力例] 0 ※AtCoderテストケースより [入力例] 10 198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501 [出力例] 830 ※AtCoderテストケースより [入力例] 5 2 1 1 3 2 [出力例] 22 [入力例] 12 7 1 8 12 10 1 7 1 2 3 2 7 [出力例] 2200 [入力例] 18 314 159 265 358 979 323 846 264 338 327 950 288 419 716 939 937 510 582 [出力例] 250796 [入力例] 50 77745357 56007369 14690761 15009778 16318676 543635 19285990 4665389 90156959 65710387 107007503 121452200 23627366 4481012 64288587 25502259 50766845 116813365 109065726 107219346 77674249 111528089 33125962 84048543 73052930 55805907 24566041 121284805 26215078 1741646 111161611 9771733 60086045 37896454 121038472 115137410 86356996 63491557 10084559 67313402 9936219 89391420 42994141 16709204 4292008 70006319 45320316 31282562 11880272 93106029 [出力例] 669312650 |
■参照サイト
AtCoder Beginner Contest 221
Binary Indexed Tree (Fenwick Tree)