稻草人
按 \(x\) 排序，可以将问题转化为寻找点对 \((i,j)\)，使得 \(y[i]<y[j]\) 且对于所有 \(i <k <j\)，都不满足 \(y[i]<y[k]<y[j]\)。
点对问题，考虑 \(CDQ\) 分治。容易发现最终对点 \(i\) 产生贡献的 \(j\) 的 \(y[j]\) 单调递减，可以使用单调栈维护。单调栈内即是右边所有可以满足限制的点。
考虑如何满足 \(y[i]<y[k]<y[j]\) 的限制。我们寻找到左边每一个点右边最近的，满足 \(h[j]>h[i]\) 的点，任何满足 \(h[k] > h[j]\) 的点应该会在 \(j\) 处被统计一次，因此 \(i\) 处不能被统计。二分得到 \(k\) 的分界点，用单调栈总点数减去分界点点数就是当前能被统计进答案的点数。
最后一个问题，对于小于 \(y[i]\) 的 \(y[j]\)，不应在单调栈中统计。因此我们要先把两边按 \(y\) 排序，然后枚举左边时依次加入右边的点。
电压
给你一 \(n\) 个点，\(m\) 条边的图，你需要给每个点黑白染色，要求有且仅有一条边两端点颜色相同。问方案数。
部分分提示性很强。
对于一棵树，每一条边都可以作为颜色相同的两端点。原因是我们一黑一白染色这棵树，然后思考改变边上一端点颜色的本质，不妨令我们改变的是深度深的点 \(u\)，那么实际上改变的是 \(u\) 及其子树内所有点的颜色。直接改即可。
看到第三个部分分，树上加一条边 \((u,v)\)。我们把树变为 dfs 树，那么多加的边必定是返祖边。不妨分类讨论：
- \(u,v\) 树上颜色不同，那么这条边必定不可变成同色。因为这样会有树上 \(u\) 到 \(v\) 路径上一条边也变为同色。同时，树上 \(u\) 到 \(v\) 路径上的所有边都不可变为同色，因为这样会使 \((u,v)\) 变为同色。
- \(u,v\) 树上颜色相同，那么这条边可以变为同色。同时，如果这条边不变为同色，树上 \(u\) 到 \(v\) 路径上的所有边必须有一条变为同色。否则 \((u,v)\) 就会变为同色。
对于多条边的情况，发现也可以归纳出上文中的限制条件，于是搞一个数据结构维护一下限制，然后枚举每条边可不可以被选即可。我用的是差分，但是常数很大。
挂饰
需要容量在 \([-n,1]\)，初始容量为 \(1\)，价值有正负的 \(01\) 背包。
\(n \le 2000\)
物品分四种
- 容量小于 \(1\)，价值为正，直接放。
- 容量为 \(1\)，价值为正，放到一个数组里从大到小排序然后做前缀和，\(pre_i\) 就是拥有 \(i\) 个钩子可以获得的最大价值
- 容量为负，价值为负，这一类物品用处是产生容量。做一个 \(01\) 背包，\(f_i\) 为产生 \(i\) 个钩子所需的最大价值。
- 容量非负，价值为负，没用，直接扔掉。
然后直接做就可以了，注意初始有容量 \(1\)。
Parking Lot
n∗m的矩阵，有一些点不能选。k次操作，每次都让一个点变成不可选，每次都问当前可选的最大正方形。
\(n,m,k \le 2000\)
蓝题？难题！
经典套路是转删为加，然后发现如果答案变大，则正方形一定包含新增的点。
我们暴力求出新增点左右两边不包含 X 的最左端和最右端，然后二分正方形的长度。判断条件为竖列上的长度不小于正方形的长度。
如何求出竖列上的长度？我们预处理出每个点向上向下不经过 X 最长能走多远，这个可以每次新增点时暴力维护。然后我们滑动窗口，窗口长度为正方形长度，找出窗口上向上走的最小值和向下走的最小值，相加即为竖列上的长度。
如何求出开始状态的正方形最大值是一个简单的动态规划，这里不再赘述。如果想看可以去最大正方形。