論一類平面點(diǎn)對(duì)曼哈頓距離問(wèn)題

1、一類平面點(diǎn)對(duì)曼哈頓距離問(wèn)題的探究,常州市第一中學(xué)陳 子 旸,曼哈頓距離問(wèn)題在信息學(xué)競(jìng)賽題目中十分常見(jiàn) 曼哈頓距離的定義：在歐幾里得空間的固定直角坐標(biāo)系上兩點(diǎn)所形成的線段對(duì)軸產(chǎn)生的投影的距離總和 討論將圍繞一類平面上最大、最小曼哈頓距離點(diǎn)對(duì)問(wèn)題展開(kāi),目錄,引例 情況一：離線查詢、無(wú)修改 情況二：在線查詢、修改 情況三：在線查詢、無(wú)修改 其他方法的討論 總結(jié),引例,magic)題目大意：在一個(gè)(k=7)維的空間中，有(n=100000)個(gè)點(diǎn)，要求求出在這些點(diǎn)對(duì)中曼哈頓距離最遠(yuǎn)的點(diǎn)對(duì)之間的曼哈頓距離,例題分析,直接暴力枚舉點(diǎn)對(duì),顯然TLE,兩點(diǎn)間曼哈頓距離的計(jì)算公式,以平面為例,例題分析,怎么處理,

2、分類討論,完全不需要,x|+|y|=|x+y,也就是說(shuō)： 如果我們計(jì)算時(shí)如果不滿足條件，所計(jì)算出的值會(huì)比真實(shí)值小，不會(huì)更新答案,例題分析,處理時(shí)，只需要分別統(tǒng)計(jì)|(x1+y1)-(x2+y2)|的最大值和|(x1-y1)-(x2-y2)|的最大值，最后再取大的作答案就行了,高維推廣處理方法類似，以三維為例，只要統(tǒng)計(jì)x+y+z,x+y-z,x-y+z,x-y-z四類情況的答案就可以了,通過(guò)引例，我們初步了解了這類問(wèn)題的特點(diǎn)，同時(shí)發(fā)現(xiàn)了解決這類問(wèn)題的一個(gè)重要的思想：去絕對(duì)值 在引例中，運(yùn)用了求最大值的條件和一個(gè)絕對(duì)值不等式，避免了分類討論。但實(shí)際運(yùn)用時(shí)往往要求最小值，我們不得不分類討論解決這類問(wèn)題

3、，接下來(lái)的部分按題目的不同要求分析了幾類不同情況,情況一：離線查詢，無(wú)修改,例題2(DONUT) 題目大意：在一個(gè)平面上有兩類點(diǎn)，。對(duì)于每個(gè)類點(diǎn)求出離他曼哈頓距離最近的A類點(diǎn)與它的曼哈頓距離，其中類和類點(diǎn)的個(gè)數(shù)都不超過(guò)50000個(gè)，點(diǎn)的坐標(biāo)范圍在長(zhǎng)整數(shù)范圍內(nèi),例題2分析,能不能套用例題1（magic）的方法,糟糕！要求最小值,x|+|y|=|x+y,例題2分析,例題2分析,有點(diǎn)像二維RMQ問(wèn)題,樹(shù)套樹(shù),二維ST,可以離線處理,例題2分析,把所有點(diǎn)按照x的值排序，依次插入處理 處理一個(gè)點(diǎn)時(shí)，所有插入的點(diǎn)的x的值都小于當(dāng)前點(diǎn)，所以只需要滿足y的條件就可以了 處理對(duì)y的限制，只需要維護(hù)一棵維護(hù)x+y

4、最大值的線段樹(shù)，能夠支持單點(diǎn)插入和區(qū)間查詢最值兩個(gè)操作就可以了,情況二：在線查詢、帶修改,例題3(DONUTEXT) 在一個(gè)平面上給定一個(gè)點(diǎn)集，可以動(dòng)態(tài)地插入或刪除點(diǎn)集中的點(diǎn)，并詢問(wèn)離點(diǎn)集中某個(gè)點(diǎn)最近的點(diǎn)到該點(diǎn)的曼哈頓距離。點(diǎn)集的大小不超過(guò)100000,例題3分析,在線，帶修改。離線算法神馬的不管用了,我們需要一個(gè)能同時(shí)處理兩個(gè)維度有序性的數(shù)據(jù)結(jié)構(gòu),有沒(méi)有想到區(qū)間第k大數(shù)問(wèn)題,例題3分析,在區(qū)間第k大數(shù)問(wèn)題中，需要同時(shí)維護(hù)數(shù)在原序列中的位置和數(shù)的大小兩個(gè)序關(guān)系 在區(qū)間第k大數(shù)問(wèn)題中，可以使用歸并樹(shù)這一結(jié)構(gòu) 下面來(lái)看一下如何把歸并樹(shù)運(yùn)用到本題中,例題3分析,把x的值作第一關(guān)鍵字（類比區(qū)間第k大數(shù)

5、問(wèn)題中數(shù)在原數(shù)組的位置），y的值作第二關(guān)鍵字（類比區(qū)間第k大數(shù)問(wèn)題中數(shù)的值），建立歸并樹(shù) 所有x符合查詢要求的點(diǎn)分布在歸并樹(shù)中的O(log2n)個(gè)區(qū)間內(nèi)，在每個(gè)區(qū)間中，y有序，可以通過(guò)二分答案找到y(tǒng)符合要求的區(qū)間。 最后，只要把歸并樹(shù)的每個(gè)節(jié)點(diǎn)用線段樹(shù)維護(hù)起來(lái)就可以了,例題3分析,于是我們?cè)贠(n log22 n)的時(shí)間復(fù)雜度 和O(n log2 n)的空間復(fù)雜度內(nèi)解決了這個(gè)問(wèn)題,情況三：在線查詢，無(wú)修改,例題4(DONUTEXT2) 題目大意：在一個(gè)平面上給定一個(gè)點(diǎn)集，查詢距離點(diǎn)（x，y）最近的點(diǎn)離它的曼哈頓距離，這里的x，y由上兩問(wèn)的答案經(jīng)過(guò)某種變化得到,例題4分析,從題面分析，這題似乎比

6、上一題目要簡(jiǎn)單，因?yàn)闆](méi)有修改操作,若果直接套用上一題的做法，那這題就沒(méi)有存在的意義了,所以一定有效率更高的算法,如何超越n log22 n,我們想到了求解區(qū)間第k大數(shù)的又一神器,劃分樹(shù),例題4分析,直觀地理解劃分樹(shù)，就是把快排的過(guò)程建成一棵樹(shù),注意：劃分樹(shù)中每個(gè)數(shù)要維護(hù)：該節(jié)點(diǎn)中，在這個(gè)數(shù)之前被分到左子區(qū)間的數(shù)的個(gè)數(shù)，例如對(duì)于根結(jié)點(diǎn)中的7，這個(gè)值就是3,例題4分析,劃分樹(shù)有很好的性質(zhì)： 根結(jié)點(diǎn)記錄原序列 下一層中被劃分成的兩個(gè)區(qū)間中的數(shù)字的相對(duì)順序與上一層相同 從一個(gè)節(jié)點(diǎn)劃分出的左子節(jié)點(diǎn)中的元素小于右子節(jié)點(diǎn)中的元素,這些性質(zhì)可以幫助我們解決例題4,例題4分析,仍然以x為第一關(guān)鍵字，以y為第二關(guān)

7、鍵字，建立劃分樹(shù)。這樣，對(duì)于一次查詢中x符合要求的點(diǎn)都在根結(jié)點(diǎn)從最左端開(kāi)始的一段連續(xù)區(qū)間內(nèi)。 這個(gè)區(qū)間內(nèi)地的點(diǎn)被按y的大小分配在兩個(gè)子區(qū)間中。依靠維護(hù)的額外信息，我們能O(1)地查出這兩個(gè)子區(qū)間具體的邊界。 如果左子區(qū)間的點(diǎn)最大的y大于查詢的點(diǎn)，直接遞歸查詢左子區(qū)間即可,例題4分析,對(duì)于左子區(qū)間最大的y小于等于查詢點(diǎn)的情況： 查詢區(qū)間被分到左子區(qū)間的部分一是一個(gè)從左子區(qū)間最左端開(kāi)始的連續(xù)區(qū)間。通過(guò)欲處理部分最大值數(shù)組可以O(shè)(1)地完成對(duì)這部分點(diǎn)的詢問(wèn)。 對(duì)于被分到右子區(qū)間的部分，遞歸查詢即可。 這樣，我們?cè)诿繉犹幚淼臅r(shí)間復(fù)雜度是O(1)，由于劃分樹(shù)只有l(wèi)og 2n層，對(duì)于一次詢問(wèn)，我們的復(fù)雜度

8、只有O(log 2n)，比例題3的方法更優(yōu)秀,例題4分析,13475,134,75,5,7,其他方法的討論,當(dāng)然，在處理這類問(wèn)題的時(shí)候還有其他方法,四分樹(shù),可持久化數(shù)據(jù)結(jié)構(gòu)（線段樹(shù),樹(shù)套樹(shù),四分樹(shù)在這類題中的運(yùn)用,回歸問(wèn)題本質(zhì)：二維RMQ查詢,一維線段樹(shù)的拓展：四分樹(shù),一個(gè)矛盾,四分樹(shù)在這類題中的運(yùn)用,巨大的空間開(kāi)銷如何解決,只把有用的節(jié)點(diǎn)建立起來(lái),可持久化數(shù)據(jù)結(jié)構(gòu)在這類問(wèn)題中的運(yùn)用,概念：可持久化數(shù)據(jù)結(jié)構(gòu)是一種特殊的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)方式。 在可持久化數(shù)據(jù)結(jié)構(gòu)中，元素一旦建立不能修改和刪除。 每次修改操作，通過(guò)建立新的元素和重利用過(guò)去已經(jīng)建立的元素實(shí)現(xiàn)。從而達(dá)到了保留數(shù)據(jù)結(jié)構(gòu)的所有時(shí)刻版本的目的

9、,可持久化線段樹(shù)簡(jiǎn)介,存儲(chǔ)結(jié)構(gòu)：指針實(shí)現(xiàn)。記錄：左、右邊界，左、右孩子，以及其他要維護(hù)的信息 建樹(shù)：調(diào)用建樹(shù)過(guò)程，返回建好的樹(shù)的根節(jié)點(diǎn) 查詢：直接查詢對(duì)應(yīng)歷史版本的根結(jié)點(diǎn)，查詢過(guò)程與普通線段樹(shù)幾乎一樣,可持久化線段樹(shù)簡(jiǎn)介,修改操作（核心） ：修改操作返回一個(gè)新的根結(jié)點(diǎn)。對(duì)一個(gè)節(jié)點(diǎn)修改操作包括了遞歸修改和更新該節(jié)點(diǎn)信息兩個(gè)過(guò)程。更新節(jié)點(diǎn)信息時(shí)，我們建立一個(gè)新的節(jié)點(diǎn)，新節(jié)點(diǎn)沒(méi)有修改過(guò)的子節(jié)點(diǎn)設(shè)置為上一個(gè)歷史版本的線段樹(shù)中的節(jié)點(diǎn)，修改過(guò)的子節(jié)點(diǎn)設(shè)置為對(duì)應(yīng)遞歸函數(shù)返回的節(jié)點(diǎn) 標(biāo)記：同樣可以實(shí)現(xiàn)，與本文關(guān)系不大,可持久化線段樹(shù)簡(jiǎn)介,在本題中的具體運(yùn)用,以分析在一個(gè)點(diǎn)左下的點(diǎn)為例，我們可以按照y坐標(biāo)的順序建立一個(gè)維護(hù)x+y最大值的線段樹(shù)。并以x坐標(biāo)的順序依次插入節(jié)點(diǎn)，這樣我們就可以得到按照x坐標(biāo)插入的線段樹(shù)的各個(gè)歷史版本，通過(guò)類似離線問(wèn)題的處理方法，解決所有詢問(wèn)，時(shí)空復(fù)雜度均為n log2 n。 是劃分樹(shù)的一種完美替代品。但對(duì)于點(diǎn)的修改會(huì)涉及到同時(shí)修改多個(gè)歷史版本的線段樹(shù)，情況復(fù)雜，這里不詳細(xì)闡述,總結(jié),本文由一道簡(jiǎn)單的例題出發(fā)，著重分析了一類有關(guān)平面上點(diǎn)對(duì)的曼哈頓距離的問(wèn)題。全文貫穿了去絕對(duì)值的思想。按