题意：给定常数 ，定义函数：
给出一个长为 的序列 。
定义 ：
即用
从左往右“求和”。
次查询 的值。
，，时限 ，空限 。
CF 版本：CF1172F
Nauuo and Bug
好题。
只需求出 “减 ” 发生的次数 ，答案即为 。
很大，考虑使用线段树维护。
对于每个节点，记
表示初始值为
时出发，从左到右加完整个区间，产生的减法次数。
可能非常大，难以存储完整的
。
- 观察：初始值越大，后面进行同样的加法，所触发的减法次数越多。
这说明 单调不降，可以将
划分为若干个递增的连续段，记
表示触发
次减法所需的最小初始值，即连续段的开头。由于最多 次减法，数组 只有 项，是可以存下来的。
考虑如何合并 两个节点到
。考虑在左右两侧各有多少次减法，可以写出
的转移：
对 分类讨论。
需要处理判据 ，移项可得 。我们可以证明右边单调不降。
- 说明：即证
。这容易理解：若想要减法多触发一次，初值至少增大 。
这说明，随着
的增大，满足判据的
的前缀单调不缩。这造就了如下的分界线：
蓝色部分判据为真，贡献为 ，红色部分判据为假，贡献为 。
当 时：
- 蓝色部分：贡献
单调增加，越靠左越小；
- 红色部分：贡献为 ，随 单调减小，越靠左越小；
于是，
上的最小值，一定在判据分界上。
要对所有 求出 ，由于判据分解随 增大单调右移，只需线性扫描即可。
建树的时空复杂度均为 。
查询时，得到
个区间，对于每个区间，需要支持给定一个初值求出通过区间后的值。直接在
数组中二分即可，复杂度 。