线段树做题单

Subarray Sum Queries II

简述题意

多次询问区间内最大子数组和。

分析

小白逛公园。

Visible Buildings Queries

简述题意

多次询问，询问一个区间内有多少个数比前面的数都大。

分析

考虑记录区间最大值和区间内的答案，询问时分讨：

1. lmax > rmax，右边一定没有贡献。
2. lmax <= rmax，相当于对于右边做线段树二分。

Increasing Array Queries

简述题意

给定数组，多次询问，问使子段 \([l, r]\) 单不降的操作数，操作是令某一个数加 1。

分析

考虑最后一定是一个前缀最大数把后面一段抹平，那么答案就和前缀最大值有关。有两种做法。

1. 线段树维护前缀最大值之和，线段树单侧递归。
2. 考虑一个点 x，会让后面一段小于 x 的变成 x，先反着扫一遍，单调栈维护一个点覆盖范围，然后令覆盖一段为"一次覆盖"，那么可以倍增做，具体而言，维护一个点往后做幂次次覆盖的长度。