元問題に色取得クエリが追加されたとして、次のクエリとクエリ後の全体出力を \(O(N+Q)\) 時間で処理することを考えます。

• 1 X: マス \(X\) にタイルが置かれていなければタイルを置き、置かれていれば取り除く。
• 2 C: タイルが置かれていないすべてのマスの色を \(C\) に変更する。
• 3 X: 現在のマス \(X\) の色を出力する。

---

クエリ処理中のマス \(i\) の色を \(a_i\) とします。

クエリ 2 が与えられるたびに \(a\) を愚直に更新すると \(O(N)\) 時間を要します。一方、クエリ 1 とクエリ 3 は、各マスのタイルの有無と色を管理していれば \(O(1)\) 時間で処理できます。

そこで、クエリ 2 による色変更を必要なタイミングまで遅延させ、クエリ 1 やクエリ 3 の処理時に必要な部分だけ色を更新することを考えます。

---

まず、クエリ 1 が与えられない場合を考えます。このとき、すべてのマスにタイルが置かれていないため、クエリ 2 が与えられるたびにすべてのマスの色が変更されます。

したがって、クエリ 3 の答えは、それ以前に与えられたクエリ 2 のうち最後のものによって決まります。クエリ 2 が一度も与えられていない場合は、初期色である a が答えになります。

よって、最後のクエリ 2 で指定された色を \(c\) として保持しておけば、クエリ 3 に対して \(c\) を出力するだけで答えられます。

---

次に、クエリ 1 が与えられる場合を考えます。

あるマス \(i\) に注目すると、クエリ 2 によって色が変更されるのは、そのマスにタイルが置かれていない期間だけです。

例えば、マス \(i\) からタイルが取り除かれた時刻を \(l_1\)、再びタイルが置かれた時刻を \(r_1\) とすると、区間 \([l_1,r_1)\) ではクエリ 2 による色変更が適用されます。その後、再びタイルが取り除かれると、次の区間 \([l_2,r_2)\) が始まります。

つまり、マス \(i\) の状態を考える際には、タイルが置かれていない期間を区切りとして考えればよいことが分かります。

重要なのは、ある期間におけるマス \(i\) の色は、その期間の開始時点の色と、その期間中に最後に与えられたクエリ 2 だけから決まるということです。

ここで、タイルが置かれると、その時点で現在の期間は終了します。このとき、その期間中に最後に与えられたクエリ 2 による色変更を反映しておけば、その後は過去の期間について考える必要がなくなります。

したがって、各マスについて、現在の期間に入ってから与えられたクエリ 2 だけを考えれば十分です。

そこで、マス \(i\) について、現在タイルが置かれていない期間の開始時刻を \(l_i\) として管理します。初期状態ではすべてのマスにタイルが置かれていないため、\(l_i=-1\) とします。一方、現在タイルが置かれている場合は \(l_i=\mathrm{INF}\) とします。

また、最後にクエリ 2 が与えられた時刻を \(p\)、そのとき指定された色を \(c\) として管理します。クエリ 2 が一度も与えられていない場合は \(p=-1\) とします。

これらを用いると、マス \(i\) の色は次のように判断できます。

• \(l_i<p\) の場合：現在タイルが置かれていない期間が始まった後にクエリ 2 が与えられているため、マス \(i\) の色は \(c\) である。
• \(l_i\ge p\) の場合：現在タイルが置かれていない期間が始まってからクエリ 2 が与えられていないか、現在タイルが置かれているため、色は \(a_i\) に保持されている。

ここで、\(l_i=-1\) は最初からタイルが置かれていない状態を表します。また、\(p=-1\) はクエリ 2 が一度も与えられていない状態を表します。したがって、初期状態では \(l_i<p\) は成立せず、\(a_i\) に保持されている初期色 a がそのまま答えになります。

この判定を用いれば、マス \(i\) の色を更新する処理 apply(i) は次のように書けます。

auto apply = [&](int i) {
    if (l[i] < p) ans[i] = c;
};

ここで、ans[i]は遅延している色変更を必要に応じて反映した、マス \(i\) の色を保持する配列です。apply(i) の実行後には ans[i] が現在の色と一致します。

この処理をクエリ 1 でタイルを置く直前、クエリ 3 で色を取得するとき、そしてすべてのクエリを処理した後に実行すればよいことになります。

---

各クエリの処理を説明します。

クエリ 1

マス \(X\) にタイルが置かれている場合、タイルを取り除きます。このとき、マス \(X\) は新たにタイルの置かれていない期間に入るため、\(l_X\) を現在のクエリ番号に更新します。

一方、マス \(X\) にタイルが置かれていない場合、タイルを置きます。このとき、タイルが置かれていない期間が終了するため、まずapply(X)を実行して遅延している色変更を反映します。その後、\(l_X=\mathrm{INF}\)とすることで、タイルが置かれている状態を表します。

いずれの場合も、タイルの有無を反転させます。

クエリ 2

このクエリでは、指定された色 \(C\) を \(c\) に、現在のクエリ番号を \(p\) に設定するだけでよいです。

クエリ 3

マス \(X\) の色を取得するには、apply(X)を実行してからans[X]を出力します。

これにより、最後のクエリ 2 による色変更が未反映であれば反映され、すでに正しい色が保持されている場合はそのまま出力されます。

---

実装例(C++)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    constexpr int INF = 1'000'000'000;
    int n, qn;
    cin >> n >> qn;

    // 最後のクエリ2の時刻と色
    int p = -1;
    char c = 'a';

    // 現在タイルが置かれていない期間の開始時刻
    // タイルが置かれている場合は INF
    vector<int> l(n, -1);

    // 各マスの色
    vector<char> ans(n, 'a');

    // 各マスにタイルが置かれているか
    vector<char> mask(n, false);

    auto apply = [&](int i)
    {
        if (l[i] < p) ans[i] = c;
    };

    for (int qi = 0; qi < qn; ++qi)
    {
        int qt;
        cin >> qt;

        if (qt == 1)
        {
            int x;
            cin >> x;
            --x;

            if (mask[x])
            {
                // タイルを取り除き、新しい期間が始まる
                l[x] = qi;
            }
            else
            {
                // タイルを置く前に色を確定させる
                apply(x);
                l[x] = INF;
            }

            mask[x] = !mask[x];
        }
        else if (qt == 2)
        {
            p = qi;
            cin >> c;
        }
        else if (qt == 3)
        {
            int x;
            cin >> x;
            --x;

            apply(x);
            cout << ans[x] << '\n';
        }
    }

    // 最終的な各マスの色を確定させて出力する
    for (int i = 0; i < n; ++i)
    {
        apply(i);
        cout << ans[i];
    }
    cout << '\n';
}

---

クエリ 1 とクエリ 3 では、定数回の代入とapplyの実行しか行わず、クエリ 2 も \(p,c\) を更新するだけなので、各クエリを \(O(1)\) 時間で処理できます。

最後に \(N\) 個のマスを走査するため、全体の時間計算量は \(O(N+Q)\) です。また、管理する配列の大きさは \(O(N)\) なので、空間計算量は \(O(N)\) です。