Readme

2250.Count-Number-of-Rectangles-Containing-Each-Point

对于矩阵而言，它有宽和高两个属性。和1996类似的思想，我们必然会将其中一个属性排序，方便我们定位，然后再解决另一个属性。

如果我们将所有的矩阵按照宽度排序之后，对于任何一个点P(x,y)，我们就可以很容易定位到哪些矩阵在宽度方向是可以包括该点的（也就是所有宽度大于等于y的矩阵），我们把这些矩阵放入一个pool中。但是在高度方向上，pool里面的这些矩阵的高度值是参差不齐的，无法快速定位有多少矩阵的高度大于等y。有人会说把这些矩阵的高度值放入一个有序的容器中，但是常规的红黑树虽然支持二分定位这些高度值里第一个大于等于y的位置，但是它无法告诉大于等于y的值总共有多少个。

此时最关键的地方就是题目给的数据范围。我们发现矩阵的高度值的范围只有100，因此我们将1到100每个刻度作为buckets来处理，即每个bucket存储有多少个对应高度值的矩阵。于是只需要最多遍历100次，就可以知道pool里矩阵的高度值有多少是大于等于y的了。

综上，我们按照横坐标从大到小处理每个点。对于任意一个点(x,y)，我们就可以把若干个符合宽度条件x>=x的矩形加入pool中，统计高度值的分布。再遍历100次，计算有多少高度值是大于等于y的。所以总的时间复杂度就是o(rectangles)*100.