题解：P14559 [ROI 2013 Day2] 快闪活动

XZhuRen · 2025-12-04 20:59:19 · 题解

像区，这个题。

称题目中的矩形为区。

题意：给你初始空平面，每次问一条区内任意一个点满足目前没有被任何一条区覆盖，然后覆盖该条区内所有点。

强化版是 rprmq2，明显不可做，考虑利用区的性质。

对行分析，列同理。

你发现同行的区只会拆成总共 O(n) 个区间，每个区间取最早覆盖的，则一条区现在是若干个不被本行干扰的区间，问题转化为：

给你初始序列赋值为无穷大，由若干操作 (p,x,t_l,t_r)，表示在时刻 [t_l,t_r] 对于位置 p 赋值 x。

若干询问为 (t,y,p_L,p_R)，表示在时刻 t 问你区间 [p_L,p_R] 内是否存在赋值 >y 的点。

这个对于行（时间）扫描线后直接单点修改，取区间 \max 及其位置即可。

实现还要离散化，我就不写了。