问个算法问题。。。。。。。

[hyousan]

有 n 个点和 n 个矩形 矩形和矩形之间可能会有重叠 点用 x,y 来表示 矩形用 x,y,w,h 表示 要求判断：任意一个点都能落在某个矩形里面,且任意一个矩形都至少包含一个点 最好能用 python 实现 有没有什么高效点的办法？

[bravecarrot]

表达能力堪忧 。 “要求判断”：后面不应该是一个命题吗？ 并没有说清楚

[Xs0ul]

n 是个什么数量级？既然矩形不带角度，那直接 x y 轴比大小也就是 n 方复杂度。

[Valyrian]

https://en.wikipedia.org/wiki/Range_searching#Orthogonal_range_searching

[aheadlead]

2000 ？代码 x2

[wnjxyk]

理解一下 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 了。