複数の \(x\) に対して、 \( \max (A_i, x)\) 操作を取り消すことを可能にするためには複雑なデータ構造が必要です。

一方で単一の \(x\) に対して \( \max(A_i, x)\) 操作を取り消すことを考えると、取り消されていない \( \max(A_i, x)\) の適応回数を使えば処理することができます。

では、分割統治アルゴリズムによる解法を解説します。

今、\(X_{ \min}\) 以上、\(X_{ \max}\) 未満の値を出力する クエリ 3 の集合が計算できたとします。

\(X_{ \textup{mid} }\) を \((X_{ \min} + X_{ \max}) / 2\) として定義します。

そのクエリ 3 の集合で問われている \(A_i\) の添字 \(i\) の集合に対して、\(X_{ \textup{mid} }\) 以上、\(X_{ \max}\) 未満のクエリ 1 の適応回数を数えつつ、クエリ 3 での出力が \(X_{\textup{mid}}\) 以上になるか未満になるかを計算します。

あとは、\(X_{\textup{mid}}\) 未満になると分かったクエリ 3 の集合と \(X_{\textup{mid}}\) 以上になると分かったクエリ 3 の集合それぞれに対して再帰的に分割統治アルゴリズムを適応すれば解くことができます。

座標圧縮や区間加算を行うので 1 イテレーションに \(O(Q \log N )\) の計算量がかかり、分割統治のために \(O(\log (\max A))\) の計算量がかかるため、全体で \(O(Q \log N \log (\max A))\) の計算量でこの問題を解くことができます。

実装例(C++, 1267msec)