P3017. Brownie Slicing G
考点
- 二分
- 前缀和
常见优化技巧_解题技巧
双指针
技巧
使用前提是，该区间已具有单调性，一般来说是贪心策略
有两种写法：
左闭右闭：两边界情况必须可取，当前条件的处理与可行性判定在本次完成
左闭右开：左边界情况可取，右边界情况不可取；
参考DFS的构造，每次处理当前条件，但可行性判定可留到下一次，精简代码逻辑；
求区间长度方便，
r - l即可
练习题
空间换时间
练习题
排序的优化
练习题
- P7910 在有序数组内修改一个数，可通过\(O\left( n \right)\)的打擂台将其放在合适的位置
最大子矩阵
技巧
共两种方法：
- 悬线法或单调栈法，依赖于长宽的大小；
- 障碍物法，依赖于障碍物的个数；
上述几个方法都是\(O\left( n^2 \right)\)的时间复杂度，所以长宽或障碍物哪个小选择哪个方法即可~
练习题
单调栈
技巧
维护区间单调性，比如”右边的元素都比我大“
和单调队列不同，偏向于破坏单调性时，反向更新单调区间内的元素
练习题
单调队列
技巧
维护区间单调性，比如”右边的元素都比我大“；常见于滑动窗口
和单调栈不同，偏向于维护区间极值
练习题
P2216 维护区间最大经典例题
P2032 维护区间最大，模板题
P1886 维护区间最大、维护区间最小的模板题
P1714 前缀和+区间最大
P1725 DP+区间最大
acwing-135 前缀和+区间最小
前缀和
技巧
多用于频繁询问满足容斥原理区间和的优化
练习题
差分
技巧
用于区间修改，\(O\left( 1 \right)\)的区间修改时间复杂度，\(O\left( n \right)\)的区间查询时间复杂度
练习题
离散化
技巧
数据点范围极其庞大，但只需要用到数据点本身，不需要在数组上表达两点之间的具体区间。