\(a_i := R_i - L_i + 1\) とします。

(海賊 \(l, l + 1, \ldots, r\) が全員 \(k\) 個以上お宝をもらうことができる)
\(\iff \min_{i=l}^r a_i - k (i - l + 1) \geq 0\)
\(\iff \min_{i=l}^r a_i - ik \geq k(1 - l)\)

です。ここで、 \(f_i(x) := a_i - ix\) とすると、

(海賊 \(l, l + 1, \ldots, r\) が全員 \(k\) 個以上お宝をもらうことができる)
\(\iff \min_{i=l}^r f_i(k) \geq k(1 - l)\)

ここで、左辺は一次関数の最小値になっているので、 Convex Hull Trick を使用することを考えましょう。

セグメント木の形を利用します。セグメント木の各ノードについて、そのノードが区間 \([L, R]\) の担当だとして、 \(f_L, f_{L+1}, \ldots, f_R\) を直線の集合として持つ Convex Hull Trick をそのノードに割り当てます。すると、 \(\min_{i=L}^R f_i(k)\) は \(O(\log^2 N)\) 時間で計算できます。あとは \(k\) を二分探索することで各クエリ \(O(\log^2 N \log (\max a))\) 程度の時間で処理することができます。

これをさらに高速化しましょう。

少し考察をすると、ある区間 \([L,R]\) において \(\min_{i=L}^R f_i(k) \geq k(1-l)\) となる \(k\) の値は \(1-l\) の減少に対して単調増加であることが分かります。よって各ノードにおいて \(l\) の降順に尺取り法を用いながらクエリを処理していくことで、ノードに割り当てられた Convex Hull Trick に含まれる直線の本数に対して線形時間でクエリ全てを処理することができます。

よってこの問題を解くことができました。計算量はセグメント木の構築に \(O(N \log N)\)、クエリ全体への回答に \(O((N+Q) \log N)\) かかります。

実装例 (C++)

（この解説の前半は Forested が書きました）