【正文】 。每天購物以后，他從以前的所有帳單中挑出兩張帳單，分別是面額最大的和面額最小的一張，并把這兩張帳單從記錄中去掉。剩下的帳單留在以后繼續(xù)統(tǒng)計(jì)。輸入的數(shù)據(jù)保證，所有 n 天的帳單總數(shù)不超過 1000000，并且每份帳單的面額值是 1 到1000000 之間的整數(shù)。保證每天總可以找到兩張帳單。 解決方法： 本題明顯地體現(xiàn)了動態(tài)維護(hù)的特性，即每天都要插入一些 面額隨機(jī)的帳單，同時(shí)還要找出最大和最小的兩張。不妨建立前面所說的線段樹，這棵線段樹的范圍是 [1， 1000000]，即我們把所有面額的帳單設(shè)為一個(gè)點(diǎn)。插入和刪除一份帳單是顯然的。如何找到最大的帳單呢？顯然，對于一個(gè)樹 v來說，如果 C[LSON[v]]0,那么樹 v 中的最小值一定在它的左子樹上。同樣，如果 C[RSON[v]]0，它的最大值在右子樹上；否則，如果 C[LSON[v]]=0，那么最大最小的兩份帳單都在右子樹上。所以線段樹的計(jì)數(shù)其實(shí)為我們提供了線索。顯然對于一個(gè)特定面額來說。它的插入，刪除，查找路徑是相 同的，長度為樹的深度，即 log1000000=20。如果總共有 N 張帳單，那么考慮極限時(shí)的復(fù)雜度為 N*20+n*20*2。這比普通排序的實(shí)現(xiàn)要簡單得多。 本題還可以采取巧妙的辦法，線段樹不一定要存帳單的具體面額。由于我們對 1000000 種面額都進(jìn)行了保存，所以線段樹顯得比較龐大。采取一種方法：我們用 hash 來保存每一種面額的帳單數(shù)目，然后對于一個(gè)具體的帳單，例如面額為 V，我們在線段樹中保存 V/100 的值，也就是說，我們把連續(xù)的 100 種面額的帳單看成是一組。由于 V 的范圍是 [1..1000000]，所以線段樹中 有 10000 個(gè)點(diǎn)。二分法與統(tǒng)計(jì)問題 江蘇淮陰中學(xué) 李睿 6 在找最大的數(shù)的時(shí)候，首先找到最小的組，然后在 hash 里對這個(gè)組進(jìn)行搜索，顯然這個(gè)搜索的規(guī)模不會超過 100。由于線段樹變小了，所以樹的深度只有 14左右，整個(gè)問題的復(fù)雜度極限為 N*14+n*14*100*2，對于問題的規(guī)模來說，仍然是高效率的。但這樣做比前種方法在一定程度上節(jié)省了空間。同時(shí)實(shí)際上也提醒了我們對線段樹應(yīng)該加以靈活的應(yīng)用。 二 一種解決動態(tài)統(tǒng)計(jì)的靜態(tài)方法 問題的提出 [例二 ] IOI2022 MOBILES 正如在摘要中所說的，這類題目的意思非常簡單明了 ，而且用幾個(gè)小循環(huán)就可以解決。但是面對可能將要處理的規(guī)模，我們卻望而卻步了，因?yàn)楹唵蔚膶?shí)現(xiàn)效率實(shí)在太低了。本題的一種完美解決方法用到了一種特殊的結(jié)構(gòu)定義。問題是二維的，注意到降格的思想，我們對一維的問題進(jìn)行討論，然后只要稍微進(jìn)行推廣。 一維的序列求和問題是這樣的 ：設(shè)序列的元素存儲在 a[]中， a 的下標(biāo)是 1..n的正整數(shù)，需要?jiǎng)討B(tài)地更新某個(gè) a[x]的值，同時(shí)要求出 a[x1]到 a[y1]這一段所有元素的和。這個(gè)問題與 MOBILES 問題實(shí)際上提法是一樣的。 數(shù)據(jù)結(jié)構(gòu)的構(gòu)造和設(shè)想 本題利用前面講的線段樹 實(shí)際上就可以得到高效地解決。因?yàn)槲覀冎烙?jì)算a[x1]到 a[y1]這一段所有元素的和，可以用 sum(1,y1)sum(1,x11)，即用部分和求差的技術(shù)。而求 sum(1,x)這種形式在線段樹上是容易快速得到的。并且修改元素的值的方法也類似。這里不詳細(xì)說明。我們希望再構(gòu)造一種特殊的形式，因?yàn)樗膶?shí)現(xiàn)比線段樹要來得簡單得多。同時(shí)這種思想也是非常有趣和巧妙的。 對于序列 a[]，我們設(shè)一個(gè)數(shù)組 C， 其中 ][]1^2[][ iakiaiC ????? ?（ k 為i 在二進(jìn)制下末尾 0 的個(gè)數(shù)）。于是我們的操作顯然與這個(gè)特定 的 C 有著特殊的聯(lián)系。那么在這個(gè)用來記錄的數(shù)組中， C[K]到底是怎樣的表現(xiàn)呢？舉一個(gè)例子，C[56]，將 56 寫成二進(jìn)制的形式為 111000，那么 C[56]表示的最小的數(shù)是 110001，即 49， C[56]表示的是 a[49]到 a[56]的所有元素的和?？梢园l(fā)現(xiàn) C 的每個(gè)元素表示是無具體規(guī)律的，例如對 C[7]，它只能表示 a[7]的值。 此種數(shù)據(jù)結(jié)構(gòu)的維護(hù) 也許你已經(jīng)注意到了，對 C 的定義非常奇特，似乎看不出什么規(guī)律。下面將具體研究 C 的特性，考察如何在其中修改一個(gè)元素的值，以及如何求部分和，之后我們會發(fā)現(xiàn)， C 的功用是非常的巧妙的。 在一個(gè) N*N 的方格中，開始每個(gè)格子里的數(shù)都是 0?，F(xiàn)在動態(tài)地提出一些問題和修改：提問的形式是求某一個(gè)特定的子矩陣 (x1,y1)(x2,y2)中所有元素的和；修改的規(guī)則是指定某一個(gè)格子 (x,y)，在 (x,y)中的格子元素上加上或者減去一個(gè)特定的值 A?，F(xiàn)在要求你能對每個(gè)提問作出正確的回答。 1≤ N≤ 1024,提問和修改的總數(shù)可能達(dá)到60000 條。 二分法與統(tǒng)計(jì)問題 江蘇淮陰中學(xué) 李睿 7 如何計(jì)算 C[x]對應(yīng)的 2^k？ k 為 x 在二進(jìn)制數(shù)下末尾 0 的個(gè)數(shù)。 由定義可以看出，這一計(jì)算是經(jīng)常用到的。有無簡單的操作可以得到這個(gè)結(jié)果呢？我們可以利用這樣一個(gè)計(jì)算式子： 2^k=x and (x xor (x1)) 這里巧妙地利用了位操作，只需要進(jìn)行兩步的簡單計(jì)算。其證明只要聯(lián)系位操作的具體用法以及 x 的特征就可以得到。 在下面的敘述中我們把這個(gè)計(jì)算式子用函數(shù) LOWBIT(x)來表示。 修改一個(gè) a[x]的值 在前面提出的問題中，我們其實(shí)要解決的是兩個(gè)問題：修改 a[x]的值，以 及求部分和。我們已經(jīng)借用 C 來表示 a 的一些和，所以這兩個(gè)問題的解決，就是要更新 C 的相關(guān)量。對于一個(gè) a[x]的修改，只要修改所有與之有關(guān)系，即能夠包含 a[x]的 C[i]值，那么具體哪些 C[i]是能夠包含 a[x]的呢？舉一個(gè)數(shù)為例，如x=1001010，從形式上進(jìn)行觀察，可以得到： p1= 1001010 p2= 1001100 p3= 1010000 p4= 1100000 p5=1000000 這里的每一個(gè) pi 都是能夠包含 x 的，也就是說，任意的 C[pi]的值，包含 a[x]的值。這一串?dāng)?shù)到底有什么規(guī)律呢 ?可以發(fā) 現(xiàn)： )(111PiL O W B I TPiPiPiPixP?????? 從觀察上容易看出這是正確的，從理論上也容易證明它是正確的。這些數(shù)是否包括了所有需要修改的值呢？從二進(jìn)制數(shù)的特征上考慮，可以發(fā)現(xiàn)對于任意的PiYPi+1， C[Y]所包含的值是 a[Pi +1]+…+a[ Y]。 C[Y]是不可能包含 a[x]的。 再注意觀察 P 序列的生成，我們每次其實(shí)是在最后一個(gè) 1 上進(jìn)位得到下一個(gè)數(shù)。所以 P 序列所含的數(shù)最多為 lgn，這里 n 是 a 表的長度，或者說是 C 表的長度。因?yàn)槲覀冇涗浀闹凳?C[1]—C[n]，當(dāng) P 序列中產(chǎn)生的數(shù)大于 n 時(shí)，我 們已經(jīng)不需要繼續(xù)這個(gè)過程了。在很多情況下對 a[x]進(jìn)行修改時(shí)，涉及到的 P 序列長度要遠(yuǎn)小于 logn。對于一般可能遇到的 n 來說，都是幾步之內(nèi)就可以完成的。修改一個(gè)元素 a[x]，使其加上 A，變成 a[x]+A，可以有如下的過程： procedure UPDATA(x,A) begin p← x while (p=n) do begin C[p]← C[p]+A p← p+LOWBIT(p) end end 二分法與統(tǒng)計(jì)問題 江蘇淮陰中學(xué) 李睿 8 計(jì)算一個(gè)提問 [x,y]的結(jié)果： 我們下面來解決求部分和的問題。根據(jù)以往的經(jīng)驗(yàn)，把這個(gè)問題轉(zhuǎn)化成為求sum(1,y)sum(1,x1)。那么如何根據(jù) C 的值來求一個(gè) sum（ 1,x)呢？容易得到如下過程。 這個(gè)過程與 UPDATA 十分類似 ，很容易理解。同時(shí)，它的復(fù)雜度顯然是 lgn。每次解答一個(gè)提問時(shí)，只要執(zhí)行 SUM 兩次，然后相減。所以一次提問需要的操作次數(shù)為 2logn。 通過上兩步的分析，我們發(fā)現(xiàn)，動態(tài)維護(hù)數(shù)組以及求和過程的復(fù)雜度通過 C的巧妙定義都降到了 logn。這個(gè)結(jié)果是非常令人驚喜和滿意的。 應(yīng)用的分析 對于我們提出的一維問題，用前面介紹的兩個(gè)函數(shù)就可以輕易地解決了。注意我們所需要消耗的內(nèi)存僅是一個(gè)很單一的數(shù)組，它的構(gòu)造比起線段樹來說要簡單得多（很明顯，這個(gè)問題也可以用前面的線段樹結(jié)構(gòu)來解決）。 只要把這個(gè)一維的問題很 好地推廣到二維，就可以解決 IOI2022 的 MOBILES問題。如何推廣呢？注意在 MOBILES 問題中我們要修改的是 a[x,y]的值，那么模仿一維問題的解法，可以將 C[x,y]定義為： yiyL O W B I TyxixL O W B I TxjiayxC ????????? ? 1)(,1)(],[],[ 其中 其具體的修改和求和過程實(shí)際上是一維過程的嵌套。這里省略其具體描述?？梢园l(fā)現(xiàn)，經(jīng)過這次推廣，算法的復(fù)雜度為 log2n。而就空間而言，我們僅將一維數(shù)組簡單地變?yōu)槎S數(shù)組，推廣的耗費(fèi)是比較低的。 可以嘗試類似地建立二維線段樹來解決這個(gè)問題，它的復(fù)雜性要比這種靜態(tài)的方法高得多。 在 IOI2022 的競賽規(guī)則中，將 MOBILES 一題的內(nèi)存限制在 5Mb。用本節(jié)介紹的方法，只需要 4Mb 的 C 數(shù)組以及一些零散的變量。而如果用蠻力建立第一節(jié)中的線段樹，其解決問題的瓶頸是可想而知的。 這種特殊的統(tǒng)計(jì)方法對于本題很有優(yōu)勢，同時(shí)它推廣到高維時(shí)比較方便，是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é) 李睿