【AtCoder】ABC157E 「 Simple String Queries 」Python解説 - Qiita

E.Simple String Queries 問題ページ 難易度 : 1443 考察 type1 は 一点更新、type2は 区間取得 問題です。したがって、このクエリを高速に処理するためには Segment Tree を利用するのが良さそうです。 あとは、区間に登場するアルファベットの種類をどうやって管理するかを考えます。これにはいくつかの手段があります。 解法➀ アルファベットごとにセグ木を持つ 欲張って全てのアルファベットについて同時に考えようとするから状況が難しくなっています。 それよりも、アルファベットごとに独立に考えるほうが簡単です。つまり、区間 $[l,r)$ 内に対象のアルファベットが含まれるか(存在するか) を求めることにします。 そのためにはアルファベットごとに管理仕分ける必要があるので、26本のセグメントツリーを作成します。 $S[i] = a $ なら $a$ に