説明のため、クエリ \(i\) が時刻 \(i\) に行われるとします。

考察

各マス \(x=1,2,\dots, N\) に対して、マス \(x\) にタイルが置かれているかどうかは、タイプ1のクエリ 1 x が行われるたびに切り替わります。

したがって、マス \(x\) にタイルが置かれていない時間帯はいくつかの区間に分けることができます。

その区間の総数は合計で見ると高々 \(N+Q\) です。なぜなら、区間の総数は最初で \(N\) 個であり、クエリ1が来るたびに高々 \(1\) 個しか増えないからです。

これに注目して、計算量がそれに依存した解法がないかを考えます。

解法

各マス \(x\) について、タイルが置かれていない時間のいくつかの区間の中で、タイプ2を行った最後のクエリを求めればよいです。

そのために、時間の区間 \([L,R)\) （\(L\) 以上 \(R\) 未満）に対して、その中でクエリ2があるかどうか、そしてあるなら最後のものは何かを探します。

それを高速に求めるには、いろいろな方法がありますが、次の2つを紹介します。

• クエリ2が行われた時間を昇順に記録した配列を用意する。二分探索を用いて \(R\) 未満の最大の要素を求める。それが \(L\) 以上ならそれが最後のタイプ2のクエリであり、そうでないなら区間にクエリ2は存在しない。計算量は \(O(\log Q)\) である。
• 前計算によって、各時刻 \(k=1,2,\dots, Q+1\) に対して、それ以前（\(k\) ちょうどを含まない）の最後のクエリ2が何であるかの配列を累積和的に求める。その後、区間 \([L,R)\) に対しては配列の \(R\) 番目の要素を参照し、あとは先ほどと同様である。計算量は前計算 \(O(Q)\)、各区間の処理あたり \(O(1)\) である。

前者の解法だと時間計算量は \(O((N+Q) \log Q)\) になり、後者の解法だと時間計算量は \(O(N+Q)\) です。

実装

累積和的に前計算する方法で実装しました

C++, 1064 Byte, 48ms

Python3, 584 Byte, 413ms