有很多矩形，矩形可能會重疊，又有很多點(diǎn)分散在平面上，求每一個點(diǎn)被多少個矩形覆蓋？

方法1：

參考：http://dongxicheng.org/structure/segment-tree/

總體思想是，如果線段樹種的一個節(jié)點(diǎn)，就是這整個區(qū)間都在要插入的邊內(nèi)，則這個節(jié)點(diǎn)的計數(shù)加1

給一個n*n的方格棋盤，初始時每個格子都是白色。現(xiàn)在要刷M次黑色或白色的油漆。每次刷漆的區(qū)域都是一個平行棋盤邊緣的矩形區(qū)域。

輸入n,M,以及每次刷漆的區(qū)域和顏色，輸出刷了M次之后棋盤上還有多少個棋格是白色。

[問題分析]

首先我們從簡單入手，考慮一維的問題。即對于一個長度為n的白色線段，對它進(jìn)行M次修改（每次更新某一子區(qū)域的顏色）。問最后還剩下的白色區(qū)域有多長。

對于這個問題，很容易想到建立一棵線段樹的模型。復(fù)雜度為O(Mlgn)。

擴(kuò)展到二維，需要把線段樹進(jìn)行調(diào)整，即首先在橫坐標(biāo)上建立線段樹，它的每個節(jié)點(diǎn)是一棵建立在縱坐標(biāo)上的線段樹（即樹中有樹。稱為二維線段樹）。復(fù)雜度為O(M(logn)^2)。

方法2：

對矩形排序，如果左邊界相同，按照右邊界排序。

給點(diǎn)一個點(diǎn)(x,y)

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

總結(jié)

以上是生活随笔為你收集整理的求点被多少个矩形覆盖的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。