8.29集训

做了一道题 传纸条， 分别有\(n^4\)的做法，\(n^3\)的做法（都是dp

开始只会\(n^4\)，经过优化，因为\(x_1+y_1-x_2=y_1\)所以可以优化成三维

又因为这道题的数组只跟临近的数据有关系，可以弄成变相的滚动数组

空间少了不少，但是复杂度和\(n^3\)一模一样

学了个小东西，悬线法

可以解决以下三个问题

• 需要在扫描序列时维护单调的信息
• 可以使用单调栈解决
• 不需要在单调栈上二分

悬线，就是一条竖线，这条竖线有初始位置和高度两个性质，可以在其上端点不超过当前位置的矩形高度的情况下左右移动。

对于一条悬线，我们在这条上端点不超过当前位置的矩形高度且不移出边界的前提下，将这条悬线左右移动，求出其最多能向左和向右扩展到何处，此时这条悬线扫过的面积就是包含这条悬线的尽可能大的矩形。容易发现，最大子矩形必定是包含一条初始位置为高度为i的悬线。枚举实现这个过程的时间复杂度为 \(O(n^2)\)，但是我们可以用悬线法将其优化到\(O(n)\)

有例题：

Largest Rectangle in a Histogram，最大子矩形，一开始初始化的时候必须让左边界和右边界都为i

然后每次更新\(l[i]\;to\;l[a[i]-1]\)，r数组同理

如果说，还学习了什么的话，只有“主席树”了

每次修改都是logn，是一个多维的数据结构

前人经验：不要吝啬空间