Nuts 2

以下の $2$ つの配列を用意します。

• $A[i]$ : 重さが $i$ であるような木の実の個数
• $B[i]$ : 重さが $i$ であるような木の実の重さの合計

$t = 3$ のクエリにおいて、明らかに重さが小さい木の実から順に取っていくことが最適です。

そうすると、$B$ の累積和について二分探索をすることによってクエリに対する答えを求めることができます。

具体的には、$\displaystyle \sum_{0 \leq i \leq k} B[i] < y$ となるような最大の $k$ を求めるとよいです。

累積和を愚直に計算すると、実行制限時間に間に合わないため、Binary Indexed Tree などのデータ構造を用いると十分高速です。

また、木の実の重さは $10^9$ までが入力で与えられるので、座標圧縮などを用いないといけないことに注意してください。

計算量は $O(Q \log^2 Q)$ となります。