セグ木
内容 ABC170のE問題(500) Smart Infantsを解いた。 コンテスト中には解けなかったが、この類の問題を解けるようになりたいので、メモで残す。 問題 園児と幼稚園がある。 園児は、それぞれどこかの幼稚園に所属していて、atcoderのrateを持っている。 *園児…
内容 ABC 157のE問題をpythonで解いた 問題 atcoder.jp 考えたこと 問題を見る感じ、seg木じゃんとなるので、segtreeで考える。 ポイント * 各ノードが、区間にどのアルファベットを持つかを記録できる必要がある。 ここで、setとかでやると、TLEしてしまう…
内容 CFのRound #590 Div3のD問題、Distinct Characters Queriesをpythonで解きました。 問題 文字列S(アルファベット小文字)とQ個のクエリが与えられる。 クエリは二種類あって、 (1 x y) -> 文字列のx番目の文字を、yに書き換える。 (2 l r) -> 文字列の[l…