这不是家庭作业问题。这是一个面试问题。我无法想出解决这个问题的好办法。
问题：
给定一个n*n(左下(0,0)，右上(n，n))网格和n个边平行于坐标轴的矩形。n个矩形的左下和右上坐标以(x1，y1)(x1’，y1’)…的形式提供。。。。(xn，yn)(xn'，yn')。有M个查询，要求覆盖坐标为(a，b)(c，d)的矩形的矩形数量。如何以有效的方式解决它？有没有一种方法可以预先计算所有坐标位置，这样我就可以在O(1)中返回答案。
限制条件：1<=n<=1000
在O(n^4)空间和O(n^2)时间中创建一个提供O(1)查找的数据结构非常简单。如果M超过O(n^2)，那么这样做可能是值得的。在O(n^ 2)空间和O(n^3)时间中创建一个在O(n)时间中提供查找的数据结构也很简单。如果M是O(n^2)，这可能是一个更好的折衷；即，分别在O(n)处进行O(n^2)次查找，需要O(n^3)次预计算时间和O(n^ 3)次时间。
对于预计算，制作一个n乘n的列表数组。设L_pq表示n乘n网格的单元p，q的列表。每个列表最多包含n个矩形，列表都按照相同的关系排序(即，如果一个列表中有Ri < Rj，则该对所在的每个列表中都有Ri < Rj)。该列表集需要时间O(n^3)来计算，取为"对于n^2个单元格中的每个C，对于n个矩形中的每个R，如果R中的C将R添加到L_C"或"对于n个长方形中的每个R，对于R中的每个单元格C，将R添加至L_C"。
给定查询(a，b，c，d)，在时间O(n)中计算列表L_ab和L_cd的交集的大小。对于O(1)查找，首先进行上述预计算，然后对每个a、b、每个c>a和d<b进行上述O(n)查询，并将结果保存在P[a、b、c、d]中，其中P是一个适当大的整数数组。
很可能存在O(n^3)或O(n^2·logn)预计算方法，该方法使用可以在O(logn)时间内进行查询的分段树、范围树或区间树。