（在学校 OJ 上打的，别想了。）

S 复赛后的第一次模拟赛。30 分钟左右就已经做出了前 3 题，然后被后面的推性质题卡住了。

得分

错因分析

D-小红的区间相交

知识点：推性质
赛时想当然地认为“两两相交”就是交集不为空。

认真读题，从题目出发推性质。

为了处理方便，将区间按照 一关、 二关升序排序。接下来，正难则反，考虑不相离、不包含的情况：

• 不相离，则 ，因为已经排过序了，所以 。
• 不相包含，则 单调不递减，否则就会出现 , 的情况。

E-小红的区间构造

知识点：构造，贪心
赛时不知道怎么构造区间最少的情况。

从差分入手，令 ，。如果 ，则说明至少有 个区间以 为右端点。否则如果 ，则说明至少有 个区间以 为左端点。用数组模拟填端点的过程，然后如果期间区间的个数超过了 ，就说明无解。如果区间个数不足，则分裂区间。

F-小红的区间创建

知识点：哈希，推性质
对于题意的理解不够。对于哈希的掌握不够深入。

首先，如果某个区间与当前的所有区间都不相交，那么它的端点一定不是任何已有区间的端点。对于当前可能对答案造成贡献的区间 和每一组 ，有：

• 包含于 ，则 均属于 。
• 包含 ，则 均不属于 。
• 与 ，则 均不属于 。 所以， 所属的区间一样。

不妨将每个点所属的区间哈希起来，那么哈希值相同且不为端点的点可以两两配对，作为区间的左右端点。用 map 统计哈希值对应的点个数，每个区间对应一个哈希值。具体实现方法很多，可以类似差分的思想做，定义 为每个区间对应的哈希值， 为差分数组， 便对应操作 ，。