【正文】 ow]x) now← now*2 else now← now*2+1 until false return ans end 二分法與統(tǒng)計(jì)問題 江蘇淮陰中學(xué) 李睿 13 中介紹的方法，而且它對內(nèi)存的消耗也是 1 個單一的數(shù)組，可以很容易地推廣到二維解決 MOBILES 的問題，最后主要的內(nèi)存消耗也是 4Mb 的靜態(tài)數(shù)組，而它的效率也是較高的。你的任務(wù)就是計(jì)算最多能得到多少個采金點(diǎn)。坐標(biāo)范圍是 (30 000=x,y=30 000)。可以發(fā)現(xiàn)，每個點(diǎn)進(jìn)出要處理的帶狀區(qū)域各一次。 得到大致算法如下： 將所有的點(diǎn)事件映射到 y 坐標(biāo)中，最多有 n=15000 個點(diǎn)，所以可能有 30000個不同的坐標(biāo)，將這些值建立一棵可用以統(tǒng)計(jì)的二叉排序樹，即 BUILD。 MAXSUM的計(jì)算實(shí)際上是一個動態(tài)規(guī)劃的過程。整個算法的時間復(fù)雜為 O(nlgn)。實(shí)際上結(jié)合二分法，我們可以不用專門構(gòu)造出二叉樹的結(jié)構(gòu)。因?yàn)閮H由二分查找的性質(zhì)可得，最多 logn 次查找就可以找到這個結(jié)點(diǎn)，即對于某個固定值的修改僅跟 logn 個結(jié)點(diǎn)有一定的關(guān)系。 虛實(shí)現(xiàn)實(shí)際上省去了構(gòu)造，因而它在實(shí)現(xiàn)上進(jìn)一步簡單化了。這樣可以使得對于任意的 (xi≤ xj ,yi≤ yj),有 i≤ j。整個動態(tài)規(guī)劃算法是這樣實(shí)現(xiàn)的： function INSERTANDGET(y):integer begin l← 1,r← n ans← 0 while (l=r) do begin m=(l+r) div 2 if y=V[m] LESS[m]← LESS[m]+1 if y=V[m] ans← ans+LESS[m] if y =V[m] break if yV[m] then r ← m –1 else l← m+1 end return ans end 二分法與統(tǒng)計(jì)問題 江蘇淮陰中學(xué) 李睿 19 這一程序非常短小精悍，其中的奧妙還是不少的。b[j]是所有長度為 j 的下降序列中，末尾數(shù)最大的那個序列的代表。 如果前面的情況都不存在，我們肯定可以找到一個 j,2≤ j≤ L,有 b[j1]a[x],b[j]≤ a[x]，這時分析， a[x]必然接在 b[j1]后面，新成一個新的長度為 j 的序列。 這時我們就要利用本節(jié)提到的二 分法了。這是一個有趣的命題。這幾節(jié)中提到的方法基本相似，在各節(jié)中具體討論了不同的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)方法，因此也可以說本文是以技巧為主的。 j← 1,k← ans while (j≤ k) do begin m ← (j+k) div 2 if b[m]a[i] j← m+1 else k← m1 end if jans ans← ans+1 b[j]←a[i] 二分法與統(tǒng)計(jì)問題 江蘇淮陰中學(xué) 李睿 22 參考書目 [1]IOI99 中國集訓(xùn)隊(duì)論文 陳宏 《數(shù)據(jù)結(jié)構(gòu)的選擇和效率》 [2]《計(jì)算幾何 —算法分析與設(shè)計(jì)》清華大學(xué)出版社 [3]《算法與數(shù)據(jù)結(jié)構(gòu)（第二版）》電子工業(yè)出版社 [4]USACO training gate Dynamic Programming資料 [5]IOI2022 試題分析（第二版） 。 [小結(jié) ] 本文圍繞的是統(tǒng)計(jì)問題的解決。 本題還有有趣的地方，在用 b 求得最長下降序列長度的同時，我們也完成了對 a 序列用最少的不下降序列進(jìn)行覆蓋的 構(gòu)造。 x 處以前對應(yīng)的最長下降序列長度為 M[x]=j。這時 b[L+1]=a[x],即 a[x]作為長度為 L+1 的序列的代表，同時 L 應(yīng)該增加 1。我們讓 P 選擇這些所有可能解中末尾數(shù)最大的，也就是說在處理完 a[1..x1]之后，對于所有長度為 M[x]1 的下降序列， P[x]的決策只跟其中末尾最大的一個有關(guān)，其余的同樣長度的序列我們不需要關(guān)心它了。現(xiàn)在以求最長下降序列（嚴(yán)格下降）為例，來說明怎樣用 O(nlogn)來解決它。現(xiàn)在我們要用虛實(shí)現(xiàn)來解決這個算法，使得它的時間復(fù)雜度為 O(nlogn)。這樣我們就省去了構(gòu)造。對于一個表 {1， 3， 4， 8， 9}的二分查找，等價(jià)于在如下圖的二叉排序樹上進(jìn)行查找： function BinSearch(x):integer begin l← 1,r← n while (l=r) do begin m← (l+r) div 2 if (V[m]=x) return m if (V[m]x) r← m1 else l← m+1 end end 二分法與統(tǒng)計(jì)問題 江蘇淮陰中學(xué) 李睿 17 9 8 3 1 4 或者用另外一種解釋說， m 取中間的值，即為一棵樹的樹根，它左邊的所有元素即 [l,m1]構(gòu)成了其左子樹上的形態(tài)，而 [m+1,r]構(gòu)成了右子樹上的形態(tài)。 四 虛二叉樹 從第三節(jié)的介紹中可以看到二叉樹是一種非常實(shí)用的靜態(tài)處理方法。有了這個過程以后，很容易完成整個算法，只要先將所有的點(diǎn)按照橫坐標(biāo)先排序，然后利用兩條掃描線 L1 和 L2 進(jìn)行掃描。 仔細(xì)分析這個過程，它有兩個部分，首先向下找到 y 所在的結(jié)點(diǎn)，然后再向上，對路徑上的每個點(diǎn)的相關(guān)量進(jìn)行修改。 通過這步巧妙的轉(zhuǎn)換，我們可以用前面的二叉排序樹來實(shí)現(xiàn) y 坐標(biāo)的點(diǎn)事件處理。 L2 在 L1 前面動，通過調(diào)整，使得 L1 到 L2 的距離不大于 S。接下來一行是整數(shù) n (1=n=15 000)，表示采金點(diǎn)的總數(shù)。老師傅可以自己選擇這塊地。只要將剛才 LESS 的定義作一點(diǎn)變化，令它為根及其左樹上所有點(diǎn)上的權(quán)和。插入一個點(diǎn)有如下過程： 我們可以在 logn 時間內(nèi)動態(tài)維護(hù) SUM,其過程與 value 的查找是同步的。只要從先序遍歷的第一個結(jié)點(diǎn)開始，每次找到它的后繼。這里我們選擇靜態(tài)結(jié)構(gòu)作為對二插樹的支持。線段樹上的一個結(jié)點(diǎn)分裂為兩個半?yún)^(qū)間的時候?qū)嶋H上是通過一個中間點(diǎn)來分割的，那么在點(diǎn)的統(tǒng)計(jì)問題中，只要保留這樣的分割點(diǎn)就可以了。 這種特殊的統(tǒng)計(jì)方法對于本題很有優(yōu)勢，同時它推廣到高維時比較方便，是function SUM(x) begin ans ← 0 p ← x while (p0) do begin ans← ans+C[p] p← pLOWBIT(p) end return ans end 二分法與統(tǒng)計(jì)問題 江蘇淮陰中學(xué) 李睿 9 前面所涉及的線段樹不可比的。如何推廣呢？注意在 MOBILES 問題中我們要修改的是 a[x,y]的值，那么模仿一維問題的解法，可以將 C[x,y]定義為： yiyL O W B I TyxixL O W B I TxjiayxC ????????? ? 1)(,1)(],[],[ 其中 其具體的修改和求和過程實(shí)際上是一維過程的嵌套。同時，它的復(fù)雜度顯然是 lgn。所以 P 序列所含的數(shù)最多為 lgn，這里 n 是 a 表的長度，或者說是 C 表的長度。 在下面的敘述中我們把這個計(jì)算式子用函數(shù) LOWBIT(x)來表示。 在一個 N*N 的方格中，開始每個格子里的數(shù)都是 0。我們希望再構(gòu)造一種特殊的形式，因?yàn)樗膶?shí)現(xiàn)比線段樹要來得簡單得多。問題是二維的，注意到降格的思想，我們對一維的問題進(jìn)行討論，然后只要稍微進(jìn)行推廣。由于 V 的范圍是 [1..1000000]，所以線段樹中 有 10000 個點(diǎn)。所以線段樹的計(jì)數(shù)其實(shí)為我們提供了線索。剩下的帳單留在以后繼續(xù)統(tǒng)計(jì)。如下圖： [1 ,1 0 ] [1 ,4] [5 ,1 0 ] [1 ,2] [3 ,4] [5 ,7] [8 ,1 0 ] [1 ] [2 ] [3 ] [4 ] [5 ， 6] [7 ] [8 ,9 ] [1 0 ] [8 ] [5 ] [6 ] [9 ] 原線段數(shù)記錄基數(shù)的 C[v]這時就可以用來計(jì)算落在定區(qū)間內(nèi)的點(diǎn)個數(shù)了。v) begin if c≤B[v] and E[v]≤ d then C[v] ← C[v]1 else if c? ?2/])[][( vEvB ? then DELETE(c,d。這里不再深入列舉。這樣才能保證線段樹的維護(hù)是正確的。 if d? ?2/])[][( vEvB ? then INSERT(c,d。 注意，這只是線段樹的基本結(jié)構(gòu)。 Count:integer。對于每一個內(nèi)部結(jié)點(diǎn) ba1，設(shè)根為 [a,b]的線段樹為 T(a,b),則進(jìn)一步將此線段樹分為左子樹 T(a,(a+b)/2),以及右子樹T((a+b)/2,b),直到分裂為一個初等區(qū)間為止。由于線段是可以互相覆蓋的，有時需要動態(tài)地取線段的并，例如取得并區(qū)間的總長度，或者并區(qū)間的個數(shù)等等。二分法與統(tǒng)計(jì)問題 江蘇淮陰中學(xué) 李睿 1 二分法與統(tǒng)計(jì)問題 淮陰中學(xué) 李睿 [關(guān)鍵字 ] 線段樹 二叉樹 二分法 [摘要 ] 我們經(jīng)常遇到統(tǒng)計(jì)的