wnjxyk
2018-12-08 09:33:45 +08:00
理解一下 Problem Statements，有 n 个点(x, y)、m 个矩形(x, y, w, h)，试问当前图形是否满足 每个点都至少被一个矩形包含 且 每个矩形都包含至少一个点。
假设 n 与 m 都是 1e5 的数量级别的，这个问题可以使用 O(nlogn)的复杂度解决。我们分`每个点至少被一个矩形包含`与`每个矩形都至少包含一个点`这两个部分解决。
首先的首先，如果坐标的数值范围大的可怕，坐标离散化是必须的。
每个点至少被一个矩形包含：
这个问题可以使用扫描线+树状数组（区间修改单点查询）解决。
我们把矩形拆成(x, y)-(x+w, y)的入边与(x, y+h)-(x+w,y+h)的出边两种。然后把入边、出边与点混在一起按照 y 的值排序（如果点和边的 y 值相同，那么要保证入边<点<出边这种顺序）。
按照 y 值从小到大的顺序便利这个对象组，当遇到一个入边(x, y)-(x+w, y)的时候，我们对树状数组的[x, x+w]范围区间+1，遇到一个出边(x, y)-(x+w, y)的时候，我们对树状数组的[x, x+w]范围区间-1。
当遇到点(x, y)的时候，我们查询树状数组位置 x 的值，假设为 p，就表示这个点就被 p 个矩形包含。如果 p=0，那就 GG 啦，直接返回 NO。
每个矩形都至少包含一个点：
这个问题，我们直接使用可持久化线段树来解决。
我们把矩形(x, y, w, h)的排序关键值设为 y+h，点(x, y)的排序关键值设为 y，然后把点和矩形混在一起排序（如果关键值相同，我们保证点<矩形）
接下来，我们建立一颗可持久化线段树 tree_0，然后关键值从小到大的顺序便利这个对象组。每遍历一个新的离散化之后的 y 值 y0，我们就从 tree_{y}创建一个新的可持久化线段树 tree_{y0+1}。如果当前是一个点(x, y)，我们对当前可持久化数据结构的 x 位置+1，如果当前是一个矩形(x, y, w, h)，我们在 tree_{y+h}-tree_{y-1}这个线段树上查询区间[x, x+w]的和 p，p 表示这个矩形包含点的数量，如果 p=0 就 GG 啦，返回 NO。
如果这两个条件都满足就 YES 了。