小課題 5 までの考察は公式解説のものとします．結局，次の操作を高速に行いたいです．

整数列 $A$ がある．ある値 $B_j$ について，以下の操作を行いたい．
$1$ 以上である $A_i$ を大きい順に $B_j$ 個まで取り出す．取り出した $A_i$ をデクリメントする．

これをデータ構造で高速化することを考えます．

\(A\) は常に sort されているとして，\(A\) に対する数列 \(D = (D_0, D_1, \cdots, D_{N - 1})\) を以下のように定めます．

• \(D_0 = A_1\)
• \(D_i = A_{i + 1} - A_i\) (\(i > 0\))

また，\(1\) 以上である \(A_i\) を大きい順に \(B_j\) 個取り出したとき，\(A_i\) の値の分布は次のようになります．ここで，取り出した \(A_i\) の値の min を \(m\) とし，\(A_i = m\) となる \(i\) の個数を \(c\) とします．

• $A_i = m$ となる $A_i$ は $c$ 個あるが，その一部．
• $A_i > m$ となる $A_i$ の全て．

これらをデクリメントしたとき，\(D\) の変化は定数個となることが分かります．また，\(m\) や \(c\) は \(D\) を Segment Tree に載せることで二分探索などで求めることができます．

よって，\(O(N \log N + M (\log N + \log M))\) などで解くことができます．