C++の練習を兼ねて, AtCoder Beginner Contest 174 の 問題F (Range Set Query) を解いてみた.
■感想.
1. 方針が見えなかったので, 解説を参照して実装したところ, 何とか, AC版となった.
2. Binary Indexed Tree の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 174 解説をご覧下さい.
■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 |
// ロジック一部修正の上, 再提出. // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using T3 = tuple<int, int, int>; #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 pb push_back #define all(x) x.begin(), x.end() int c[505050]; // 石情報. int q[505050]; // クエリ回答. // handmade04, random06 で, WA版 となったため, ロジック変更. // int b[505050]; // 良い玉. map<int, int> b; // 良い玉. // 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, Q, x, y; scanf("%d %d", &N, &Q); rep(i, N) scanf("%d", &c[i]); vector<T3> v; rep(i, Q){ scanf("%d %d", &x, &y); x--, y--; v.emplace_back(x, y, i); } // 2. sort. // https://www.geeksforgeeks.org/sorting-vector-tuple-c-ascending-order/ sort(all(v), [](const T3 &a, const T3 &b){ return get<1>(a) < get<1>(b); }); // for(auto &p : v) printf("l=%d r=%d i=%d\n", get<0>(p), get<1>(p), get<2>(p)); // 3. クエリの回答を作成. BIT<int> ft(N + 1); int bef = 0, cur = 0; assert(v.size() == Q); rep(j, Q){ int l = get<0>(v[j]); int r = get<1>(v[j]); int i = get<2>(v[j]); // 今回分更新. cur = r; // 良い玉の集合を更新. repx(k, bef, cur + 1){ // 前回以前に, 良い玉をチェック済か否か. if(b.count(c[k])){ int at = b[c[k]]; if(at < k){ // 良い玉の場所を解除. int tSum = ft.sum(at, at + 1); assert(tSum <= 1); if(tSum) ft.add(at, -1); // 良い玉の出現位置を更新. b[c[k]] = k; // 良い玉の場所を更新. ft.add(k, 1); // printf("k=%d tSum=%d c[k]=%d b=%d at=%d\n", k, tSum, c[k], b[c[k]], at); // puts("----------"); // rep(m, N + 1) printf("%d ", ft.sum(m, m + 1)); // puts("\n----------"); } }else{ // 良い玉の出現位置を更新. b[c[k]] = k; // 良い玉の場所を更新. ft.add(k, 1); } } // クエリ回答. q[i] = ft.sum(l, r + 1); // 前回分更新. bef = cur; } // 4. 出力. rep(i, Q) printf("%d\n", q[i]); 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 |
[入力例] 4 3 1 2 1 3 1 3 2 4 3 3 [出力例] 2 3 1 ※AtCoderテストケースより [入力例] 10 10 2 5 6 5 2 1 7 9 7 2 5 5 2 4 6 7 2 2 7 8 7 9 1 8 6 9 8 10 6 8 [出力例] 1 2 2 1 2 2 6 3 3 3 ※AtCoderテストケースより [入力例] 15 10 6 5 5 2 2 3 4 5 5 6 6 1 1 2 1 7 7 7 9 9 15 1 5 3 4 3 7 3 10 5 8 5 12 4 7 [出力例] 1 2 4 3 2 4 5 4 6 3 [入力例] 25 17 8 6 6 3 2 3 4 5 5 6 6 1 1 2 10 10 1 2 6 7 8 9 9 8 3 8 11 6 7 11 17 10 18 2 19 1 1 1 6 1 8 1 10 13 19 20 25 17 25 3 17 5 17 2 10 3 18 6 22 [出力例] 2 2 4 4 7 1 4 6 6 4 4 7 7 7 5 7 10 |
■参照サイト
AtCoder Beginner Contest 174
Binary Indexed Tree (Fenwick Tree)