- 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分治,简单容斥
- 本质即为计算是否有时间在它后面并且与它有交的矩形
- 考虑计算在它后面与它无交的矩形个数即为上下左右(二维偏序)减去四个角的矩形个数(三维偏序)
- 解决即可