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