まずクエリを先読みして逆から処理することで、クエリ 1 を削除クエリに読み替えることができます。

さらに数列 \(A\) の代わりに座標圧縮をしたヒストグラム \(C: [0, N[ \rightarrow \mathbb{N}\) を管理しておくと、クエリ 1 は \(C(x)\) を \(1\) 減少させるクエリになり、クエリ 2 はクエリの \(x\) からスタートして、\(k\) を超えないように \(C(x)\) を集計しつつ \(x\) を減少させていくクエリになります、クエリ 3 もクエリ 2 と同様です。

クエリ 2, 3 では、\(C\) の非零点のみからなる dancing links と、零点最寄りの 非零点に誘導するための union find を使うと、\(x\) の変化回数が \(k\) で押さえられます。以上により \(O(Q(\log Q + k))\) で解くことができました。

提出: https://atcoder.jp/contests/abc241/submissions/46723997