P11695 [JRKSJ ExR] 昼寝 题解

前言

忙里偷闲做 ds！

题意简述：支持加 / 删区间和查询当前所有被 $[l,r]$ 包含的区间的并是否等于 $[l,r]$ 。

数据范围不小，很难在线维护，考虑离线分治。

设当前分治区间为 $[sl,sr]$ ，中点为 $mid$ ，在这一层分治内部处理所有被 $[sl,sr]$ 完全包含并跨过 $mid$ 的询问，其余询问递归处理。考虑两类区间对询问的贡献：跨过 $mid$ 或被 $[l,mid]$ 和 $(mid,r]$ 完全包含。

对于这类区间，当前的目标是对每个询问 $[ql,qr]$ 找到所有被 $[ql,qr]$ 包含的区间中，极左的能贡献的位置 $tl$ 与极右的能贡献的位置 $tr$ 。下面以求解 $tl$ 为例， $tr$ 与 $tl$ 本质相同：

首先对时间轴扫描线，在区间被删除的时候撤销其贡献。需要用线段树和可删堆 / set 对每个 $l$ 维护当前还存在的以 $l$ 为左端点的区间 $[l,r]$ 中 $r$ 的最小值。假设现在扫描到时间轴的位置为 $i$ ，需要进行以下操作：

若第 $i$ 个操作加入了当前需要处理的区间 $[l,r]$ ，在第 $l$ 个可删堆中插入 $r$ ，将线段树下标为 $l$ 的位置修改为这个堆里的 $\min$ 。
若第 $i$ 个操作是当前需要处理的询问 $[l,r]$ ，则在线段树上二分 $[l,mid]$ 内第一个值 $\leq r$ 的下标，赋值为这个询问的 $tl$ 。
若第 $i$ 个操作删除了当前需要处理的区间 $[l,r]$ ，则在第 $l$ 个可删堆中删除 $r$ ，将线段树下标为 $l$ 的位置更新成这个堆里的 $\min$ （如果堆是空的则更新为极大值）。

可见线段树需要支持的功能为单点修改 / 区间 $\min$ / 区间二分第一个 $\leq k$ 的数（求解 $tr$ 时正好相反，维护的是区间 $\max$ 以及区间二分最后一个 $\geq k$ 的数，同时可删堆维护的也变成了最大值）。

这次我们更换扫描线的维度，对序列下标扫描线，线段树维护的下标则是时间轴。还是以处理完全在左边的操作区间为例，完全在右边的情况本质相同。

首先将要处理的询问和区间全部按左端点升序排序，从左到右扫描线。考虑使用这些区间依次往右覆盖询问，遇到询问时判断这个询问被覆盖的值是否小于它的 $tl-1$ ，若是则不合法。假设当前扫描到序列下标为 $i$ ，需要进行的操作为：

遍历所有左端点为 $i$ 的询问。设询问编号为 $t$ ，在线段树上将下标为 $t$ 的位置修改为极小值，这样就可以撤销所有左端点 $<i$ 的区间对这个询问的贡献。
遍历所有左端点为 $i$ 的区间 $[i,r]$ 。设其在时间轴上出现的时间区间为 $[lt,rt]$ 。在线段树上将 $[lt,rt]$ 对 $r$ 取 $\max$ 。
不断取出当前线段树上的最小值，设最小值为 $x$ ，取到最小值的位置为 $id$ ，循环终止条件为 $x\geq i$ （若 $x<i$ ，代表 $i$ 这个下标未被覆盖，则左端点 $\geq i+1$ 的区间就无法对其造成贡献了）。若 $tl_{id}>i$ ，这个询问就是不合法的。特别地，若没有任何区间覆盖过这个询问，取出的 $x$ 会是极小值。特判一下，这种情况合法的条件为 $tl_{id}=l_{id}$ 。

这一步需要一个支持区间取 $\max$ ，单点修改和全局最小值的线段树（同样的，求解右区间时也正好相反）。

至此，所有情况的贡献都被我们统计完成。这题里扫描线的各种用法感觉很有启发性。

link，11 kb，太恐怖。