- p4577
- 开始的想法是维护每个节点上的权值线段树上存的局部最优解，然后用线段树合并进行转移
- 然后写+调了整整1个半小时后，我发现这个做法是可行的，但是实现极其复杂，故我开始思考了新的做法
- 可以沿用 \(O (N \log{N})\) 的求 LIS 的做法
- 故可以对每个节点维护一个 multiset ，再使用启发式合并即可
- P5873 cdq分治
- 很容易想到这是一个 三维偏序 问题
- 以时间为第一维
- 计算 新加入点对答案的贡献
- 则为所有 \(x1<=x<=x2，y1<=y<=y2\) 的矩阵总数
- 计算 新加入矩阵对答案的贡献
- 则为所有 \(x1<=x<=x2, y1<=y<=y2\) 的点的总数
- 考虑用 cdq 分治差分解决即可
- 计算 新加入点对答案的贡献
- P7312 cdq分治，简单容斥
- 本质即为计算是否有时间在它后面并且与它有交的矩形
- 考虑计算在它后面与它无交的矩形个数即为上下左右（二维偏序）减去四个角的矩形个数（三维偏序）
- 解决即可