This problem can be solved with a data structure called merge-sort tree or wavelet matrix.

• The merge-sort tree was featured in ABC339-G too, so see also the editorial for that problem.
• The wavelet matrix is AtCoder Algorithm Lecture in great detail, so please refer to it. (Unfortunately, the article is currently only in Japanese.)

Both solutions end up in the same solution, but explanation using the wavelet matrix is rather complicated, so we will explain based on the merge-sort tree.

\(\mathrm{O}(Q \log^3 N)\) solution (TLE expected)

Suppose that \(A\) were static, i.e. never updated.
Construct a merge-sort tree against \(A\). For example, if \(A=(1,6,5,4,9,8,2,7)\), the merge sort tree is as follows. (Intuitively, the indices \(i\) are merged while sorted by \(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]

When querying about a certain segment, say \([2,6]\), against the merge-sort tree, we notice that the segment \([2,6]\) is divided into several components:

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

Moreover, the indices are sorted within each component in ascending order of \(A_i\). Thus, we can combine binary search and cumulative sums to process a query like “find the number / sum of elements with \(A_i \geq x\) within \([l, r]\)” in \(\mathrm{O}(\log N)\) time. This is a general application of a merge-sort tree. Replacing the cumulative sums to a Fenwick tree also enables element-update of \(A\), but the time complexity worsens to \(\mathrm{O}(\log^2 N)\).

Let us consider a solution using this merge-sort tree.

For each query, the answer can be found by binary searching a value \(x\) such that “eating all sweets with deliciousness \(x\) or greater results in a total deliciousness of \(k\) or greater.” Each step of the binary search costs \(\mathrm{O}(\log^2 N)\), so the complexity per query is \(\mathrm{O}(\log^3 N)\). This is not fast enough, and most implementation would receives a TLE (Time Limit Exceeded) verdict. (If you have a wavelet matrix fast enough, this approach also allows to pass.)

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

Let us modify how we maintain the merge-sort tree. An ordinary merge-sort tree represent the process of “merging indices \(i\) in the order of the values \(A_i\).” Let us flip the index and value: that is, we consider the process of “merging values \(A_i\) in the order of the indices \(A_i\).”
For example, \(A=(1,6,5,4,9,8,2,7)\) is represented as follows:

[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]

In our original problem, we want to know: “at what moment does the total deliciousness exceed \(k\), when more delicious sweets are eaten earlier?” Say we want to query against segment \([2,6]\).
On the merge-sort tree, this segment \([2,6]\) corresponds to those surrounded by round parenthesis. Interestingly, the elements in segment \([2,6]\) form a subarray on each segment, because the values are sorted by the indices.

[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)]

Using this property, the query asking “at what moment the total deliciousness exceeds \(k\), when more delicious sweets are eaten earlier” can be answered in \(\mathrm{O}(\log^2 N)\) by traversing the merge-sort tree from the root toward the leaves while using binary search and cumulative sums.
If we want to support updates, we can simply replace the cumulative sums with Fenwick trees, and the time complexity is still \(\mathrm{O}(\log^2 N)\). (The complexity never worsens, thanks to the coincidence of the structure of binary search and the Fenwick tree.) Hence, the problem can be solved in \(\mathrm{O}(Q \log^2 N)\) time, which is fast enough. (For some languages, the time limit might be tight and requires to use a wavelet matrix.)
In conclusion, we introduced a technique of reducing the complexity by swapping the indices and values.