この問題は merge-sort tree あるいは wavelet matrix と呼ばれるデータ構造を工夫して用いると解くことが出来る問題です。

• merge-sort tree は ABC339-G で出題されているのでそちらの解説も参考にしてみてください。
• wavelet matrix は AtCoder Algorithm Lecture で非常に詳しく説明されています。ぜひ参考にしてみてください。

どちらの解法もやることは同じですが、wavelet matrix を用いて説明するのは少し大変なので merge-sort tree ベースで説明します。

\(\mathrm{O}(Q \log^3 N)\) 解法 (TLE 想定)

\(A\) が static である、すなわち更新が来ない場合を考えてみましょう。
\(A\) に対する merge-sort tree を構築します。例えば \(A=(1,6,5,4,9,8,2,7)\) の場合は以下のようになります。(index \(i\) たちを \(A_i\) の値の順でマージしていくイメージ)

[1 7 4 3 2 8 6 5]
[1 4 3 2] | [7 8 6 5]
[1 2] | [4 3] | [6 5] | [7 8]
[1] | [2] | [3] | [4] | [5] | [6] | [7] | [8]

merge-sort tree を利用すると、例えば区間 \([2,6]\) の情報を取得したい時に、merge sort tree 上で区間 \([2,6]\) は

• [2]
• [4,3]
• [6,5]

という風にいくつかの区間に分割されていて、かつ区間内では index が \(A_i\) の値順に並んでいます。よって二分探索および累積和と併用すると「\([l,r]\) 内で \(A_i \geq x\) である要素の個数 / 総和は？」といったクエリが \(\mathrm{O}(\log N)\) で処理できます。これが merge-sort tree の一般的な用法です。累積和を fenwick tree に置き換えると \(A\) の要素の更新クエリにも対応できますが、計算量は \(\mathrm{O}(\log^2 N)\) に悪化します。

この merge-sort tree を利用した解法を考えてみましょう。

クエリが来た時に、値 \(x\) であって「美味しさ \(x\) 以上のお菓子を全て食べると、食べたお菓子の美味しさの総和が \(k\) を超える」ような \(x\) を二分探索で求めれば答えがわかります。二分探索 1 回あたりの計算量は上記の通り \(\mathrm{O}(\log^2 N)\) なので、クエリ 1 回あたりの計算量は \(\mathrm{O}(\log^3 N)\) になります。これは十分高速とは言えず、大抵の実装では TLE してしまうようです。(十分高速な wavelet matrix を持っていればこの方針でも通ります。)

\(\mathrm{O}(Q \log^2 N)\) 解法 (AC)

merge-sort tree の持ち方に少し工夫を加えてみます。一般的な merge-sort tree は先に述べた通り「index \(i\) たちを \(A_i\) の値の順でマージ」でしたが、これを逆転させてみましょう。つまり、「値 \(A_i\) たちを index \(i\) の順でマージ」という風に index と値を逆転させてソートしてみます。
例えば \(A=(1,6,5,4,9,8,2,7)\) の場合は以下のようになります。

[1 6 5 4 9 8 2 7]
[1 5 4 2] | [6 9 8 7]
[1 2] | [5 4] | [6 7] | [9 8]
[1] [2] [4] [5] [6] [7] [8] [9]

さて、今回の問題では、「美味しい方からお菓子を食べていった時に \(k\) を超えるのはどのタイミングか？」を知りたいです。例えば区間 \([2,6]\) にクエリを飛ばすことを考えましょう。
この時、区間 \([2,6]\) は merge-sort tree 上では以下の丸括弧で囲まれた部分になります。面白い事実として、全てのノードにおいて、区間 \([2,6]\) に含まれる要素は連続部分列をなしています。これは index の順にソートしていることから従います。

[1 (6 5 4 9 8) 2 7]
[1 (5 4) 2] | [(6 9 8) 7]
[1 2] | [(5 4)] | [(6) 7] | [(9 8)]
[1] [2] [(4)] [(5)] [(6)] [7] [(8)] [(9)]

この性質を利用すると、「区間 \([l,r]\) 内のお菓子を大きい方から食べていった時に \(k\) を超えるのはどのタイミングか？」というクエリに対して、二分探索+累積和を使いながら merge-sort tree を根から葉に向かって降りていく\(\mathrm{O}(\log^2 N)\) 解法が従います。
更新がある場合も累積和の部分を fenwick tree に置き換えればよく、計算量は \(\mathrm{O}(\log^2 N)\) のままです。(二分探索と fenwick tree の計算量がかみ合うので計算量が悪化しない) よってこの問題を \(\mathrm{O}(Q \log^2 N)\) で解くことが出来て、これは十分高速です。(ただし言語によっては同じ内容を wavelet matrix を用いて実装しないと TL が厳しいかもしれません)
というわけで、index と値を入れ替えて管理するだけで計算量が落ちるという面白いテクニックの紹介でした。