C++の練習を兼ねて, AtCoder Beginner Contest 185 の 問題F (Range Xor Query) を解いてみた.
■感想.
1. 問題F は, 遅延評価セグメント木 で, 解けるのでは？と気付けたので, AC版となったと思う.
2. 遅延評価セグメント木が必要なため, 下記のライブラリを拝借させて頂いた.
3. 遅延評価セグメント木 が 復習できたので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Beginner Contest 185 解説 の 各リンク を ご覧下さい.
■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 |
// 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--) LL a[303030]; // ※※※ 以下のライブラリを使用(一部改変) ※※※. // 遅延評価セグメント木をソラで書きたいあなたに. // http://tsutaj.hatenablog.com/entry/2017/03/30/224339 // http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2236726 struct LazySegmentTree{ private: int n; vector<LL> node, lazy; public: LazySegmentTree(vector<LL> v){ int sz = (int)v.size(); n = 1; while(n < sz) n *= 2; node.resize(2 * n - 1); lazy.resize(2 * n - 1, 0); // 元配列 の 値 を, セグメント木のノード に 保存. rep(i, sz) node[i + n - 1] = v[i]; repr(i, n - 2, 0) node[i] = node[i * 2 + 1] ^ node[i * 2 + 2]; } void eval(int k, int l, int r){ if(lazy[k] != 0) { node[k] ^= lazy[k]; if(r - l > 1) { lazy[2 * k + 1] ^= lazy[k] / 2; lazy[2 * k + 2] ^= lazy[k] / 2; } lazy[k] = 0; } } void update(int a, int b, LL x, int k = 0, int l = 0, int r = -1){ if(r < 0) r = n; eval(k, l, r); if(b <= l || r <= a) return; if(a <= l && r <= b){ lazy[k] += (r - l) * x; eval(k, l, r); }else{ update(a, b, x, 2 * k + 1, l, (l + r) / 2); update(a, b, x, 2 * k + 2, (l + r) / 2, r); node[k] = node[2 * k + 1] ^ node[2 * k + 2]; } } LL query(int a, int b, int k = 0, int l = 0, int r = -1){ if(r < 0) r = n; eval(k, l, r); if(b <= l || r <= a) return 0; if(a <= l && r <= b) return node[k]; LL vl = query(a, b, 2 * k + 1, l, (l + r) / 2); LL vr = query(a, b, 2 * k + 2, (l + r) / 2, r); return vl ^ vr; } }; int main(){ // 1. 入力情報. int N, Q; scanf("%d %d", &N, &Q); rep(i, N) scanf("%lld", &a[i]); // 2. 遅延評価セグメント木. LazySegmentTree seg(vector<LL>(N, 0)); rep(i, N) seg.update(i, i + 1, a[i]); // 3. クエリ回答. rep(i, Q){ int t; scanf("%d", &t); // t = 1 の 場合. if(t == 1){ int x; LL y; scanf("%d %lld", &x, &y); x--; seg.update(x, x + 1, y); } // t = 2 の 場合. if(t == 2){ int x, y; scanf("%d %d", &x, &y); x--; LL ans = seg.query(x, y); 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 60 61 62 63 64 65 66 67 68 69 70 71 |
[入力例] 3 4 1 2 3 2 1 3 2 2 3 1 2 3 2 2 3 [出力例] 0 1 2 ※AtCoderテストケースより [入力例] 10 10 0 5 3 4 7 0 0 0 1 0 1 10 7 2 8 9 2 3 6 2 1 6 2 1 10 1 9 4 1 6 1 1 6 3 1 1 7 2 3 5 [出力例] 1 0 5 3 0 ※AtCoderテストケースより [入力例] 30 20 1826625 6307608 5102954 7621862 10442296 3996426 7264299 12297597 3899350 1158993 4758228 6186721 8596313 4652633 10830571 11187561 6764085 5527929 901727 8816692 11165577 86493 6917229 11527084 9530288 6398081 5903621 5639709 6921806 10252436 1 2 856073 2 7 10 1 7 3884061 2 1 9 1 10 11884054 1 12 11042007 2 5 12 1 15 7837903 2 1 30 2 8 21 1 23 9323052 2 7 13 1 19 2973277 2 9 17 1 25 9489387 2 21 27 1 3 1658936 2 2 12 1 18 7234258 2 11 22 [出力例] 16756177 3770995 7115274 4338650 3498989 4985953 16484875 14235238 2194607 5451091 |