制約による \(D _ i\) の最大値を \(D _ {\text{max}}\) とおきます。

\(B \leq 10\ 000\) かつ \(D _ i \leq 10\ 000\) の場合を遅延セグメント木で処理します。

まず、 \(1\) つのクエリに対してリンゴを出荷できるかどうかを判定することを考えます。幅 \(B\) のある閉区間内に \(N_i\) 個のリンゴがあればよいですが、リンゴを幅 \(B\) の閉区間で表すことにすると、 \(N_i\) 個のリンゴが重なる点があるかどうかの判定に変換されます。これは区間加算区間最大値クエリですから、遅延セグメント木で実現できます。

次に、条件を満たす点のうち最も右にあるものを求める必要があります。これは遅延セグメント木上の二分探索で実現できます。

最後に、濃さがある値以下のリンゴを \(N _ i\) 個、濃さの大きい順に取り除きます。リンゴの濃さの取得には上述の遅延セグメント木もしくは C++ の multiset を用いるとよいです。

以上、全体の計算量は \(O( B + D _ { \text{max} } + M \log ( B + D _ { \text{max} } + M ) )\) です。

以上のことは、作用の伝播を行わないセグメント木（ Starry Sky 木として知られる）を用いても可能です。

\(B\) や \(D _ {\text{max}}\) を大きくしても、遅延セグメント木でアクセスするノードの個数はあまり増加しないので、これをポインタ木にしてノードの生成を遅延させると、全体の計算量は \(O(M \log ( B + D _ { \text{max} } + M ) )\) となります。実装によってはメモリが不足しますが、このとき遅延セグメント木の代わりに Starry Sky 木を使うと生成するノード数が少なくなる場合があります。この解法で満点を得られます。

解答例