本文共 469 字，大约阅读时间需要 1 分钟。

有很多矩形，矩形可能会重叠，又有很多点分散在平面上，求每一个点被多少个矩形覆盖？

方法1：

参考：

总体思想是，如果线段树种的一个节点，就是这整个区间都在要插入的边内，则这个节点的计数加1

给一个n*n的方格棋盘，初始时每个格子都是白色。现在要刷M次黑色或白色的油漆。每次刷漆的区域都是一个平行棋盘边缘的矩形区域。

输入n,M,以及每次刷漆的区域和颜色，输出刷了M次之后棋盘上还有多少个棋格是白色。

[问题分析]

首先我们从简单入手，考虑一维的问题。即对于一个长度为n的白色线段，对它进行M次修改（每次更新某一子区域的颜色）。问最后还剩下的白色区域有多长。

对于这个问题，很容易想到建立一棵线段树的模型。复杂度为O(Mlgn)。

扩展到二维，需要把线段树进行调整，即首先在横坐标上建立线段树，它的每个节点是一棵建立在纵坐标上的线段树（即树中有树。称为二维线段树）。复杂度为O(M(logn)^2)。

方法2：

对矩形排序，如果左边界相同，按照右边界排序。

给点一个点(x,y)

二分查找左边界小于x的，然后就可以删除右边的矩形，对y也同理

转载地址：http://oteti.baihongyu.com/