10 15

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