Subarray Sum Queries II
简述题意
多次询问区间内最大子数组和。
分析
小白逛公园。
Visible Buildings Queries
简述题意
多次询问，询问一个区间内有多少个数比前面的数都大。
分析
考虑记录区间最大值和区间内的答案，询问时分讨：
- lmax > rmax，右边一定没有贡献。
- lmax <= rmax，相当于对于右边做线段树二分。
Increasing Array Queries
简述题意
给定数组，多次询问，问使子段 \([l, r]\) 单不降的操作数，操作是令某一个数加 1。
分析
考虑最后一定是一个前缀最大数把后面一段抹平，那么答案就和前缀最大值有关。有两种做法。
- 线段树维护前缀最大值之和，线段树单侧递归。
- 考虑一个点 x，会让后面一段小于 x 的变成 x，先反着扫一遍，单调栈维护一个点覆盖范围，然后令覆盖一段为"一次覆盖"，那么可以倍增做，具体而言，维护一个点往后做幂次次覆盖的长度。