您可以以O(N log N)的方式完成以下操作。
首先，“挤压”您的y坐标。也就是说，将所有y坐标（顶部和底部）一起排序在一个数组中，然后用排好序的数组中的索引替换矩形描述中的坐标。现在您拥有所有的y都是从0到2n-1的整数，而且问题的答案没有改变（如果您有相等的y，请参见下文）。
现在，您可以将平面分成2n-1个单位高度的条纹，并且每个矩形完全跨越几个条纹。为这些条纹准备一个线段树。（有关线段树概述，请参见this link。）
然后，在同一个数组中按左右边界对所有x坐标进行排序，并保留每个坐标来自哪个矩形以及它是左边界还是右边界的信息。
接着，遍历这个列表，在遍历过程中，维护当前“活动”的所有矩形的列表，也就是说，您已经看到了左边界但是还没有看到右边界的矩形。
更准确地说，在你的线段树中，你需要为每个条纹保留多少个覆盖它的活动矩形。当你遇到左边界时，你需要为相应矩形底部和顶部之间的所有条纹添加1。当你遇到右边界时，你需要减去1。使用线段树的质量更新（延迟传播），可以在O(log N)内完成加法和减法。
实际上检查你所需的内容，当你遇到左边界时，在添加1之前，请检查底部和顶部之间是否至少有一个具有非零覆盖范围的条纹。这可以通过在线段树中执行间隔查询的总和来在O(log N)内完成。如果此间隔上的总和大于0，则存在交叉部分。
squeeze y's
sort all x's
t = segment tree on 2n-1 cells
for all x's
r = rectangle for which this x is
if this is left boundary
if t.sum(r.bottom, r.top-1)>0 // O(log N) request
you have occurence
t.add(r.bottom, r.top-1, 1) // O(log N) request
else
t.subtract(r.bottom, r.top-1) // O(log N) request
你应该仔细实现它，考虑是否认为触摸是相交的，这将影响你对相等数字的处理。如果你认为触摸是相交的，那么你所需要做的就是，在排序y时，确保所有具有相同坐标的点中，所有顶部都在底部之后，同样地，在排序x时，确保所有相等的x中，所有左边的都在右边之前。
