做题的时候研究了很久题解，故写一发，感觉这题的思考很有深度。还有就是我并不是很会贪心。

看到这题首先将 排序，然后发现肯定有 ，否则必然无解。

首先考虑 怎么做，此时没有 的限制，我们只需最大化 的个数。那我们从小到大枚举 ，找到在区间内最小的没有匹配过的 ，将 与这个 匹配。显然这个贪心策略对后续匹配的影响是最小的（用 Hall 定理的说法，就是对 后面的左部点的可用邻域影响最小）。在造出这个最大匹配后，容易发现那些非匹配点按照原顺序填肯定也还能满足 。

现在考虑加入了 之后的限制。假如我们已经知道了每个点是选择 还是 ，那判断此时能不能凑出完美匹配的方法就是选出一个值域区间 ，如果完全包含在 内的线段数 （即区间 或 的数量）大于区间内的 数量，那肯定没有完美匹配。否则根据 Hall 定理一定存在完美匹配。

那我们考虑枚举这个 ，那么对于 的位置，其对 ”完全包含在 内的线段数“ 不会产生影响，而对于 的位置，其选 就会让区间内的线段数 。我们希望区间内的线段数量不超过某个值。其实就是让满足 的 中，选 的个数不超过某个值。所以此时有 个限制，每个限制形如 ，表示 中只能有不超过 个选择 。

进一步地发现，如果 ，那么 的限制是没用的。只要 固定，这个 对应的 就固定了。所以我们在众多的 中选择使得 限制最紧的那一个。 的值域区间只会产生 个 的限制。

当然如果最终的选法只满足上述 个限制，可能导致一些 的区间限制不满足。

对于一个 的限制，如果其不被满足，那选择 的 对其是否满足不产生影响，只可能是选择 的 导致的。说明如果只保留选择 的 ，这组解都不成立。这说明如果有一个 的限制不满足，可以推出这组解在不考虑 这条限制时都不成立。

综上所述，最后的解只需要满足两个条件：

1. 个 限制，表示 中有贡献的点不超过 个。
2. 每个有贡献的点都能找到一个对应的 。

那把 的贪心套进来即可。至于限制 ，在扫描 时开一棵线段树维护数组 。其中 表示 中还能选至多 个。当且仅当 时我们再去找匹配点， 扫到某个限制的 时单点修改。选中一个匹配点时后缀减即可。

代码：https://qoj.ac/submission/339608