CF1439C Greedy Shopping
给定一个长为 \(n\) 的单调不增的数组 \(a\)，有 \(q\) 次操作：
-
- 给出 \(x,y\)，令区间 \([1,x]\) 内的数对 \(y\) 取 \(\max\)。
-
- 给出 \(x,y\)，从左到右遍历 \([x,n]\) 内的每个数，如果 \(a_i\le y\)，那么令 \(y\leftarrow y-a_i\)，你需要回答这个过程中 \(y\) 被减了几次。
\[n,q\le 2\times 10^5\\ a_i,y\le 10^9
\]
首先有一个重要观察：至多有 \(\log y\) 段连续的数被 \(y\) 减去。
证明如下：
考虑相邻的两个数 \(a,b\)，满足 \(y\ge a\)，但是 \(y-a < b\)，这个时候 \(a\) 会成为一个连续操作段的结尾。
由于 \(b\le a\)，所以 \(y-a < a\)，即 \(y < 2a\)，那么有，
\[y-a < y-\dfrac y2 = \dfrac y2
\]
所以在这个过程中 \(y\) 至少会减少一半。那么显然最多只有 \(\log_2 y\) 段。
有了这个性质，我们就可以通过线段树简单维护来支持 \(\mathcal O(\log n)\) 处理一段连续的操作。
那么总时间复杂度: \(\mathcal O(q\log n\log V)\)，其中 \(V\) 为值域。