クエリバケット分割によるシンプルな解法を紹介します．公式解説よりも計算量は悪いです．

バケットサイズ \(B (\leq N)\) をとって， \(B\) 個ずつのクエリに分けて処理します．クエリは先読みできませんが，現在保持している \(N\) 要素のうちで \(B\) 回のクエリで削除される可能性がある要素は \(B\) 個しかありません．そこで要素を次の \(2\) 種に分けて管理します．

• グループ 1：削除されるかもしれない \(B\) 要素
• グループ 2：絶対に削除されない要素 \(N-B\) 要素

途中で追加される要素はグループ 1 側で管理します．

\(0\leq k\leq B\) に対してグループ 1 から \(k\) 個選んだときにグループ 2 からいくつ選ぶべきか，そのときの答がどうなるかが （convex-arbitrary の）min convolution で計算できます．これをクエリバケットごとに最初に \(1\) 回やります．

あとはグループ 1 に対する追加削除しながら，求値ではグループ \(1\) から選ぶ要素数を全探索することでクエリに答えられます．

主な計算量は，

• 強さに関するソート：最初に \(1\) 回やる以外は常にソート順を保つように実装できる．
  • グループ 2 に対する追加削除には \(O(B)\) 時間かける．全体で \(O(QB)\) 時間．
  • クエリバケットの最後にクエリ 1, 2 をマージするが，ソート列のマージなので \(O(N)\) 時間．全体で \(O(NQ/B)\) 時間．
• グループ 1, 2 への分割：std::nth_element などによりバケットごとに \(O(N)\) 時間，全体で \(O(NQ/B)\) 時間．
  • 礼儀正しさに関するソートも強さと同様に管理するという方法もあります．
• min convolution：実装により \(O(N)\) 時間や \(O(N\log N)\) 時間．全体で \(O(NQ/B)\) 時間や \(O(NQ\log N/B)\) 時間．
  • SMAWK, monotone minima などを想定，オーダーには差があるが本解説執筆時点では Library Checker の最速提出は後者です．

これで全体の計算量は \(O(Q\sqrt{N})\) 時間や \(O(Q\sqrt{N\log N})\) 時間になります．これで AC 可能です．

• 解答例：https://atcoder.jp/contests/jsc2025-final/submissions/68717590

他にも類似の計算量の別解法はありますが，解法によっては定数倍が大きすぎて全然 AC できなかったりすると思います．