Segment Covering 题解

思路

若一个输入线段包含另一个输入线段，那么所有使用外层线段的覆盖方案都可按“是否再选择内层线段”两两配对，奇偶贡献抵消。因此外层线段可以删除。剩余线段按左端点排序后，右端点也严格递增。

对于询问 $[l,r]$，候选线段在上述序列中连续。第一条线段必须左端点为 $l$。当一条线段已被选中，除紧随其后的线段外，其余与它相交的候选线段贡献都会抵消；于是下一条真正必须选择的线段，是当前线段右侧第一条与它不相交的线段。最终有效覆盖至多一种，答案只可能是 $-1,0,1$。

做法

令每条保留线段的父亲为它右侧第一条左端点严格大于当前右端点的线段，不存在则连向虚根。这形成一棵父指针森林。

询问时找到左端点为 $l$ 的第一条线段 $i$。若不存在、越过 $r$，或 $i$ 与 $i+1$ 无法衔接，答案为零。否则分别从 $i$ 与 $i+1$ 沿父指针向上跳到右端点不超过 $r$ 的最后节点。若两者汇合，或者都未到达右端点 $r$，答案为零；若 $i$ 一侧到达则答案为 $-1$，否则为 $1$。

小档直接枚举全部线段子集并检查并集；中档对每个询问线性沿父指针跳；满档建立父指针倍增表。

复杂度

满分算法时间复杂度为 $O((m+q)\log m)$，空间复杂度为 $O(m\log m)$。