まず自明な考察として、食べるお菓子の順番は美味しさ降順になります。以下、これを前提とします。

永続セグメント木で解ける問題に、この問題の更新無し版があることを考察の起点とします。

インデックスと美味しさの二次元で表される座標を考えます。

\( P_{x, y} \) を、 \(A_x=y\) ならば \((1, y)\) 、そうでないならば \((0, 0)\) として定義します。 また、 \((a, b) + (c, d) = (a + c, b + d)\) として定義します。
この時、 \(\sum_{x=l}^{r} \sum_{y=m}^{\infty} P_{x, y}\) の値 \((c, s)\) は、 \(A_l, A_{l+1}, \ldots, A_r\) のうち \(m\) 以上の値の個数と総和になります。

ここで、 \(s \geq k\) を満たす最大の \(m\) を二分探索で求めます。
このとき、 \(m\) より大きい値の総和は \(k\) 未満です。\(m\) より大きい値の個数と総和をそれぞれ \(c_>,s_>\) とすると、 \(s_><k\) であり、答えは

\[ c_>+\left\lceil\frac{k-s_>}{m}\right\rceil =c-\left\lfloor\frac{s-k}{m}\right\rfloor \]

となります。
よって \(P_{x, y}\) を高速に更新し、また総和の算出ができれば答えを求めることができます。

さて、この \(P_{x, y}\) を二次元セグメント木を用いて解くことを考えます。

木の高さ\(B=\lceil \log_2(A_{\max}+1) \rceil\) とおきます。
通常の二次元セグメント木では、以下の二点が問題となります。

1. \(y\) 座標の範囲が広く、全頂点を保持すると空間計算量が \(\Theta(NA_{\max})\) になる
2. 二分探索を含む計算量は最悪 \(O(\log N \log ^2 A_{\max})\) となる

まず1. については、必要なところだけ持つセグメント木を用います。
\(y\) 座標を管理するセグメント木を高さ \(B\) の完全二分木に固定し、子であって総和が \((0, 0)\) になるようなものは null にしておきます。

外側のセグメント木の各ノードが管理する要素数を \(t\) とすると、その内側の木に現れる null でない頂点数は \(O(tB)\) です。また、外側の木全体で \(t\) の総和は \(O(N \log N)\) なので、null でない頂点の個数の総和は

\[ O(NB\log N)=O(N\log N\log A_{\max}) \]

となります。

次に2. については、セグメント木上の二分探索の考え方を利用します。
セグメント木上の二分探索においては、左部分木全体が条件を満たすなら右に、そうでないなら左に探索をすることで、各判定問題の計算量を \(O(1)\) にしていました。
今回の場合は \(l \leq x \leq r\) を求めるためのセグメント木は最大 \(O(\log N)\) 本ありますが、1. の木はいずれも同じ \(y\) 座標の値域上に構築されているため、各木で同じビットを同時に探索できます。
これにより二分探索の \(\log\) を1つ減らすことができるので、クエリ辺りの計算量 \(O(\log N \log A_{\max})\) が達成できます。

点更新も、外側のセグメント木の各階層で値方向の木を1本更新するため、計算量は \(O(B\log N)\) です。したがって、初期構築を含む全体の計算量は

\[ O((N+Q)B\log N)=O((N+Q)\log N\log A_{\max}) \]

となります。