题解：P16545 [EGOI 2026] 狐狸家族 / Fox Families

GavinCQTD · 2026-07-21 14:38:10 · 题解

拿线段树做了半天，鉴定为 ds 学傻了。

考虑将现有家族看作一个整体区间。

则对于一个新区间，可能被一个现有区间整体包含（或反过来包含现有区间）。

[___________________]
    [____new____]

当然也有可能包含一个现有区间中的小区间。

[_________________]
           [___]
        [________new________]

不妨设单个家族的范围是 [L,R]，新区间 [l,r] 想要并入在第一种情况下当且仅当 L \leq l \land r \leq R 或 l \leq L \land R \leq r。显然 L 等价于家族内的 l_i 最小值，R 等价于家族内的 r_i 最大值。

对于第二种情况，首先有 R \leq r，此时只要有小区间 [p,q] 满足 l \leq p 就能合并。贪心地发现，如果家族内 p 的最大值都无法进行合并的话，情况二肯定是不行的。把新区间放在左侧也同理，因此我们只需要维护一个区间左右端点的最值，就可以 O(1) 判断一个区间是否能合并。

那对于一个新区间，如何查找可以合并的区间？

这堆判断条件不能用什么数据结构快速统计，只能一个一个判，因此考虑定一个判断顺序，使其有一个不合法的临界情况，可以直接在这里退出。

本人的考场思路太丑陋了，以下参考了 @Little_duck_GGG 佬的思路。

找找性质，考虑如下情况，我们假设 A_{l_{min}} < B_{l_{min}}。

          [______B______]
     [______A______]
[_____new_____]

假设 A 不能与新区间合并，则必有 r < A_{r_{min}}，此时若 B 能成功合并，则需要有 r \geq B_{r_{min}}，但这样的话 A 和 B 就可以合并，条件冲突。

故我们按照 l_{min} 排序后，对于一个新区间一路往右边扫到第一个失败的区间，就不用继续扫了。

向左也是一个道理，代码实现很简单。