title
给定一个非重叠轴对齐矩形的列表 rects，写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。
提示：
- 整数点是具有整数坐标的点。
- 矩形周边上的点包含在矩形覆盖的空间中。
- 第
i个矩形rects [i] = [x1，y1，x2，y2]，其中[x1，y1]是左下角的整数坐标，[x2，y2]是右上角的整数坐标。 - 每个矩形的长度和宽度不超过 2000。
1 <= rects.length <= 100pick以整数坐标数组[p_x, p_y]的形式返回一个点。pick最多被调用10000次。
示例 1：
输入:
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
输出:
[null,[4,1],[4,1],[3,3]]
示例 2：
输入:
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
输出:
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]
输入语法的说明：
输入是两个列表：调用的子例程及其参数。Solution 的构造函数有一个参数，即矩形数组 rects。pick 没有参数。参数总是用列表包装的，即使没有也是如此。
solution
蓄水池抽样，该题把随机抽样应用到了二维空间的点，这里以 pointCnt / total的概率选择当前矩形，然后在等概率选择x和y坐标。
利用前缀和做二分查找。
class Solution:
def __init__(self, rects: List[List[int]]):
self.rects = rects
self.rect2id = {}
total = 0
for i in range(len(self.rects)):
r = self.rects[i]
pcnt = (r[2] - r[0] + 1) * (r[3] - r[1] + 1)
total += pcnt
self.rect2id[total] = i
self.total = total
self.keys = list(self.rect2id.keys())
def pick(self) -> List[int]:
import random
k = random.randint(1, self.total)
import bisect
i = bisect.bisect_right(self.keys, k-1)
# print(i)
id = self.rect2id[self.keys[i]]
select = self.rects[id]
return [random.randint(select[0], select[2]), random.randint(select[1], select[3])]