C++の練習を兼ねて, AtCoder Beginner Contest 157 の 問題E (E – Simple String Queries) を解いてみた.
■感想.
1. 遅延評価セグメント木を使う必要があると思ったので, 下記のライブラリを拝借させて頂いた.
2. 遅延評価セグメント木の復習が出来たので, 良かった思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 157解説をご覧下さい.
■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 110 111 112 113 114 115 116 117 118 119 120 121 122 |
// コメント, ロジックを修正して再提出. // ※※※ 以下のライブラリを使用(一部改変) ※※※. // 遅延評価セグメント木をソラで書きたいあなたに. // http://tsutaj.hatenablog.com/entry/2017/03/30/224339 // http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2236726 #include <bits/stdc++.h> using namespace std; #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 struct LazySegmentTree{ private: int n; vector<int> node, lazy; public: LazySegmentTree(vector<int> 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, int 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] = max(node[2 * k + 1], node[2 * k + 2]); } } int 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]; int vl = query(a, b, 2 * k + 1, l, (l + r) / 2); int vr = query(a, b, 2 * k + 2, (l + r) / 2, r); return max(vl, vr); } }; int main(){ // 1. 入力情報. int N, Q; char c[505050]; scanf("%d %s %d", &N, c, &Q); // 2. 区間更新(遅延伝播セグメント木). LazySegmentTree seg(vector<int>(505050, 0)); vector<LazySegmentTree> vSeg; rep(i, 26) vSeg.pb(seg); rep(j, N) vSeg[c[j] - 'a'].update(j, j + 1, 1); // rep(i, 26){ // rep(j, N) printf("%d ", vSeg[i].query(j, j + 1)); // puts(""); // } // 3. 各クエリに回答. int n, iq, lq, rq, bef, cur, ans, bCnt, cCnt; char cq[5]; rep(i, Q){ scanf("%d", &n); if(n == 1){ scanf("%d %s", &iq, cq); iq--; // 変更前の文字. bef = c[iq] - 'a'; // 変更後の文字. cur = cq[0] - 'a'; // 変更前文字の出現個数. bCnt = vSeg[bef].query(iq, iq + 1); // 変更前文字を減算. if(bCnt > 0) vSeg[bef].update(iq, iq + 1, -1); // 変更後文字の出現個数. cCnt = vSeg[cur].query(iq, iq + 1); // 変更後文字を加算. if(cCnt == 0) vSeg[cur].update(iq, iq + 1, 1); // 文字列を, 変更後文字 に 更新. c[iq] = cq[0]; }else{ scanf("%d %d", &lq, &rq); lq--, ans = 0; // 部分文字列(区間[lq, rq]) の 種類数は？ rep(j, 26) ans += vSeg[j].query(lq, rq); // 出力. printf("%d\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 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 |
[入力例] 7 abcdbbd 6 2 3 6 1 5 z 2 1 1 1 4 a 1 7 d 2 1 7 [出力例] 3 1 5 ※AtCoderテストケースより [入力例] 1000 ggqtrvenemxwthumrlocwlctxxmbsooujmfccxllbwwykqvtwvcngsqxasbnmclqtsgsgxduumiplpoiipdwdejnmenbstbrnkbpkdgcdvdhlzeypkzakudjkzyggsfbpbivwgpsgxvkmbpgqykbzhwdagvcelocxoqxbaxzfjcccnwiwvddazswpizkwynkgavmngjvwwwzlyqvbygzwxbdvrdvodahopopgrnekzckoltfggxzaaqnzwdlxeeyxgrnkukaicrvykpylgfbgsxuthmmyehsuhioreqvlugbfeohfrenolimitmbvbwroeubkoufsmzrdlxfoakpjzvoieqvparrggzgljyytkaaikyjcpdoomeclhlczuahfdgjtcqxjztoigsrrduxhmvzxhksceuuumzlerqpomsaixwfbbjjawyqxziizpnpnhehiqxnxqfzeoruqfayxxebstkuzucanllavjsiyxhrorhgokqqdhzvfnubulwytmnqstoqsyeawpdeorrjcazpjknvofmqdapjmynbsmtisvjjqqhfgttvtzgozjnyyrulifotqwsdtvrvyadjpjwaekqpkftuiwmkswvfzgmomkoyskjgpvocsyierkwbnvbbejaaiprhsuhuntqetlchpcqklbsxapnpswhnvjufojhacomgyciblelllbtrrhilwykknjedzfqcqmurlpgbucydtlppevoupsctnefcdcfcyarhypwcughjnsaampromcofiyzklqfovbomtdmvyiujzwuuiawqufemluzzrvfyujylzmzjmocfuybaugumsnotomafbpetgakrrpngnooxvrperwzpgqssxutfjfwbaayermrhhlszodmkelfkqofufeqqdybflhcgmfwpppurkyzwptrlvvubsmvfkdhlxraxirqvvnhvagsegpkpdivdmtjeyxikbhiibhygiwumilqwzyzpgrja 100 2 85 132 1 279 a 1 302 k 1 561 v 2 10 369 2 41 126 1 213 q 1 306 d 2 43 82 1 685 o 1 195 a 1 79 l 1 710 z 1 752 n 2 21 51 2 45 172 2 64 360 1 264 y 1 19 w 2 95 182 1 176 v 1 591 c 2 46 108 2 36 413 1 742 c 2 16 31 2 35 185 2 84 376 1 101 k 1 373 x 2 47 223 1 138 t 1 622 a 1 215 t 2 3 287 1 540 e 1 456 p 2 59 386 1 787 s 1 618 k 2 63 225 1 244 k 1 603 w 1 744 u 1 734 i 2 30 308 1 342 m 1 276 p 1 764 a 2 24 174 1 156 s 2 78 180 1 650 t 1 574 z 1 621 a 1 32 v 2 73 240 1 426 p 2 1 388 1 286 r 1 777 d 2 80 254 1 704 d 2 20 185 1 532 e 1 62 l 2 50 200 1 606 w 2 82 283 2 1 98 1 608 w 1 36 x 1 553 w 2 64 195 1 739 r 2 43 300 1 99 w 1 336 g 2 89 190 2 37 242 1 212 r 1 751 j 1 624 i 2 54 205 1 298 p 2 1 128 1 764 t 2 95 152 2 31 420 1 105 l 2 2 22 1 594 r 1 406 p 2 97 130 2 43 380 1 589 u 1 112 k 1 177 g 1 505 f 2 28 147 [出力例] 22 26 25 20 16 26 26 25 22 26 10 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 25 26 26 26 26 26 26 24 26 14 19 26 26 |