这不是作业问题。它是一个面试问题。我无法为这个问题想出好的解决方案。
问题 ：
给定一个 n*n (bottom left(0,0) , top right(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^5) 时间内创建一个提供 O(1) 查找的数据结构很简单。如果 M 超过 O(n^2) 可能值得这样做。在 O(n^2) 空间和 O(n^3) 时间内创建一个在 O(n) 时间内提供查找的数据结构也很简单。如果 M 是 O(n^2)，那可能是一个更好的权衡；即，O(n^3) 预计算时间和 O(n^3) 时间用于 O(n^2) 查找，每个 O(n)。
对于预计算，创建一个 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”或“对于每个 R在 n 个矩形中，对于 R 中的每个单元格 C，将 R 添加到 L_C"。
给定一个查询 (a,b,c,d)，在 O(n) 时间内计算列表 L_ab 和 L_cd 的交集的大小。对于 O(1) 的查找，首先进行上面提到的预计算，然后对于每个 a,b，对于每个c>aand d<b，做上面提到的 O(n) 查询并将结果保存在 P[a,b,c,d]其中 P 是一个适当大的整数数组。
很可能存在 O(n^3) 或 O(n^2 · log n) 预计算方法，使用可以在 O(log n) 时间内进行查询的分段树、范围树或区间树。