クエリ \(1\) は「タイルが置かれているかどうか」の bool 列を切り替えることで \(O(1)\) で処理できそうです。

しかし、クエリ \(2\) は愚直には「すべてのマスについて、タイルが置かれているか確認し、置かれていないのであれば色を塗り替える」ことが必要です。これにより色が変わるタイルは、最悪 \(\Theta (N)\) あり、簡単には \(\Theta(NQ)\) です。

上のアルゴリズムで無駄な点を考えてみましょう。これは「毎回色を塗り直している」点です。結果として欲しいものは、最終的な色だけですから、これさえ計算できれば良いです。

様々な方法がありますが、直感的な方法としては

• クエリを前から見て、「最後にタイルが覆われているか」を求める。
• クエリを後ろから見て、色を塗るクエリが来たとき、「まだ色が塗られていない」かつ「タイルに覆われていない」マスにだけ色をぬる

ができれば、各マスについて、一度だけ色を塗ることができます。これは、具体的には次のようにすると実現できます。

「まだ色が塗られていない」かつ「タイルに覆われていない」マスの集合 \(S\) を管理して、後ろからクエリを見る。

• タイプ \(1\)

  タイルの状態を変化させる。もし \(S\) の集合を変化させるのであれば、\(S\) を更新する。

• タイプ \(2\)

  \(S\) の要素すべてに色を塗り、集合 \(S\) を空にする。

とすれば良いです。計算量は、集合の挿入・削除を \(O(1)\) とすれば \(O(Q + N)\) です。

実装例 (PyPy)

n, q = map(int, input().split())

qry = [(2, "a")]
tile = [0] * n
for i in range(q):
    t, x = input().split()
    if t == "1":
        x = int(x) - 1
        tile[x] ^= 1
        qry.append((1, x))
    else:
        qry.append((2, x))

s = set(i for i in range(n) if tile[i] == 0)
ans = [""] * n
for t, x in reversed(qry):
    if t == 1:
        if tile[x] == 0 and ans[x] == "":
            s.remove(x)
        if tile[x] and ans[x] == "":
            s.add(x)
        tile[x] ^= 1
    else:
        for i in s:
            ans[i] = x
        s.clear()

print("".join(ans))