[SHOI2009] 会场预约 题解

发布时间 2023-10-04 21:14:29作者: ft61

LG


  • 任意时刻每个点最多被一条线段覆盖
  • 暴力删每条线段是对的
  • 插入 \([l,r]\) 时需要删除的线段要么被 \([l,r]\) 包含,要么覆盖 \(l\)\(r\)

性质非常强所以做法非常多

一种比较神奇的:对于两条线段 \([l_{1},r_{1}],[l_{2},r_{2}]\),定义 <\(r_{1}<l_{2}\),即线段 \(1\) 完全在线段 \(2\) 左边。据此定义的 == 即为两线段有交

set<pair<int,int>> 维护集合 \(S\),不断 finderase 即可

code