クエリ平方分割による解法を紹介します。ただし、十分高速な言語でないと実行制限時間に間に合わせるのは厳しそうです。

与えられたクエリを、\(B\) 個ずつに分割します。\(B\) の値を適切に決め、分割したそれぞれのブロック内で工夫して処理することで、十分高速に処理することができます。以下に、その方法を記します。ただし、クエリの個数が \(B\) の倍数でない場合、1 1 1 0などの意味のないクエリを末尾に追加することにします。

重要な事実として、各ブロック内のクエリ3の個数は高々 \(B\) 個です。これは、クエリ3で質問される高々 \(B\) 項以外は真面目に処理する必要はないということです。

また、クエリ2の個数も高々 \(B\) 個です。そのため、消える可能性のある高々 \(B\) 個のクエリ以外は、消えることを考えずに処理することが可能ということです。これらを踏まえて、以下のように処理をします。

• クエリ3で質問される項を昇順に並べた列 \(p=(p_1,p_2,\dots,p_n)\) を作る。そして、\((a_1,a_2,\dots,a_n)=(A_{p_1},A_{p_2},\dots,A_{p_n})\) とした数列を作成する。これは、\(O(B\log B)\) 時間で処理できる。
• \(a\) に対して、過去に処理して、このブロックを処理するまで消えないようなクエリ1をすべて処理する。正確には、\(l<p_i<r\) であるような \(i\) すべてに対して、\(a_i:=\max(a_i,x)\) に置き換える。これは二分探索と双対セグメント木を使用することで \(O(Q \log B)\) で実現可能である。
• 多重集合の列 \(m=(\{a_1\},\{a_2\},\dots,\{a_n\})\) を作り、過去に処理して、このブロックを処理すると消えるクエリ1を処理する。正確には、\(l<p_i<r\) であるような \(i\) すべてに対して、\(m_i\) に \(x\) を追加する。このようなクエリは高々 \(B\) 個であることから、これは愚直にやっても \(O(B^2 \log B)\) で実現可能である。(多重集合は今後の処理のためにstd::multisetである必要があり、そのため \(O(\log B)\) が計算量に掛かっています)
• ブロック内のクエリを順に処理する。合計で \(O(B^2 \log B)\) 時間。
  • クエリ1では、先ほどと同じように区間内の多重集合に要素を追加する。\(O(B\log B)\) 時間
  • クエリ2では、該当するクエリ1の区間内の多重集合から \(x\) を削除する。\(O(B\log B)\) 時間
  • クエリ3では、\(p_j=i\) を満たす \(j\) に対して、\(m_j\) の最大値を出力する。\(O(\log B)\) 時間

ブロックは \(\frac{Q}{B}\) 個存在するので、計算量 \(O(\frac{Q}{B}(Q\log B+B^2 \log B))\) 時間でこの問題を解くことができました。\(B\) を \(\sqrt{Q}\) とすると、計算量は \(O(Q^{1.5}\log Q)\) となります。

この値は最大ケースで \(10^9\) 程度になってしまうものの定数倍が比較的軽いので、たとえば \(B=500\) などとすると実行制限時間に間に合わせることが可能です。

実装例 (C++23,4101ms)