ARC076D Exhausted?

题意：在数轴上有 个椅子，编号为 。椅子 的坐标为 。

现在有 个人要就座，第 个人能坐在 中的某一把椅子。每一把椅子只能做一个人。

现在要添加一些椅子（可以放在任意实数位置），让所有人都能坐下，求添加椅子的最小数目。

，时限 。

---

似乎有贪心做法，但是感觉很难想到啊……

显然可以建立一个二分图，求出最大匹配，然后给没有匹配上的人加椅子。

于是只需求该二分图的最大匹配数。

---

数据范围较大，直接优化建边配合网络硫算法并不能通过。

考虑用 定理（的推论）来求解这个二分图最大匹配。

• 结论： 二分图的最大匹配为 。

左部的 不具有任何性质，不好处理，而右部的 总是 的形式。

考虑离散化之后枚举 ，查看哪些点符合条件，复杂度至少 。

接下来我们可以钦定 ，使用数据结构维护 的 。

• 维护

  考虑一个人 邻域是 的子集的充要条件 : (二维数点)。

  若 向右移动一位，可能会使得一个新的左侧点得以满足 ，然后这个点会贡献到所有 的位置。就是前缀加。

• 维护

  事先对于每个 计算满足 的椅子数目，也就是 。

  当 向右移动一位，同样会使得一个新的椅子满足 ，触发全局减。

• 查询

  对于一个确定的 ，合法的 必须满足 ，于是就相当于区间最大值。

线段树维护即可。注意最后要与 取个 。

复杂度 （ 同阶）。