ABC157 E - Simple String Queries

問題原文

atcoder.jp

問題要旨

長さ の文字列 がある。
以下の種類がある 個のクエリを処理せよ。

1. 文字目を に変える

2. 番目から 番目まで（両端含む）に、何種類文字があるかを答える

3. 

4. は英子文字からなる

解法

こういうのは、ある場所までに文字がどのぐらい出現するか、ではなく、『各文字種がどこに出現するか』を管理するとよい。
すると更新も調査も速くできそうだというのがすっと見える。

英小文字のみ→たかだか26種類→小さい特徴的な制約！ 。。。みたいな感じですると見えやすいかも。
各文字種が 番目から 番目までにあるかどうかは、 と についてにぶたんして、範囲が潰れていないかをチェックすればいですね。

実装

セグ木26本とかset26個とかやり方はあるけど、僕はこんな感じでやった。
文字が同じ時に更新をしないのが少し鍵。PyPyでギリギリ間に合う。PythonだとTLEだった。

from bisect import bisect_left, bisect_right

N = int(input())
S = list(input())
Q = int(input())

D = {chr(ord('a') + i): [] for i in range(26)}
for i, s in enumerate(S):
    D[s].append(i)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1]), query[2]
        i -= 1
        s = S[i]
        if s == x:
            continue

        D[s].remove(i)
        next_i = bisect_left(D[x], i)
        D[x].insert(next_i, i)
        S[i] = x

    if query[0] == '2':
        l, r = int(query[1]), int(query[2])
        l, r = l - 1, r - 1
        ans = 0
        for i in range(26):
            s = chr(ord('a') + i)

            li = bisect_left(D[s], l)
            ri = bisect_right(D[s], r)

            if ri - li > 0:
                ans += 1

        print(ans)

感想

類題というか、起点となる考え方は

atcoder.jp
と似てますね

セグ木いい加減整備しないとなぁ。。。