信息學競賽中的離散化應用離散化在競賽中如果數據值的范圍很淡，但是稀疏分布。可以考慮將這有限個稀疏分散的數據映射到一個相對小的數據范圍內，以此提高算法的時空效率。這就是離散化處理。通俗的說，離散化是在不改變數據相對大小的條件下，對數據進行相應的縮小。例如：原數據：1,999,100000,15；處理后：1,3,4,2；原數據：{100,200}，{20,50000}，{1,400}；處理后：{3,4}，{2,6}，{1,5}。離散化是程序設計中一個常用的技巧，可以有效的降低時間復雜度。其基本思想就是：在眾多可能的情況中，只考慮需要用的值。離散化可以改進一個低效的算法，甚至實現根本不可能實現的算法。例如，在建造線段樹空間不夠的情況下，可以考慮離散化。離散化模板假定有一個無限長的數軸，數軸上每個坐標上的數都是0。首先進行n（1<=n<=10^5）次操作，每次操作將某一位置x（-10^9<=x<=10^9)上的數加c。接下來，進行m(1<=m<=10^5)次詢問，每個詢問包含兩個整數l和r。求出在區間[l,r]之間所有數的和。輸入第一行包含兩個整數n和m。接下來n行，每行包含兩個整數x和c。再接下來m行，每行包含兩個整數l和r。輸出共m行，每行輸出一個詢問中所求的區間內數字和。輸入樣例：輸出樣例：33812036575134678這是一道典型的單點修改，區間查詢的題目。執行n次在某位置x上的加上c，并且還詢問m次給定區間的和這種問題。這種問題的解題利器就是前綴和。此題的問題在于修改位置。題目給出的修改位置x的數據范圍，-10^9<=x<=10^9。無論是否能夠開這么大的數組，這個范圍的前綴和，預處理的時間復雜度也是10^9量級，是競賽中無法接受的。而實際需要處理的數據量n,m都是10^5量級,相對10^9來說很小。只需要聚焦處理這10^5量級的數據即可。這就是離散化的基礎。首先可以明確，在這題中離散化的對象是數軸的坐標。所以對于輸入的位置x和對應的數值c，只需要把數軸下標放到數組f[n]中即可，這里的f[n]為離散化后的重映射數組。實操中，可以用結構體之類的方法創建一個二元組用于存儲坐標x和對應的數值c。同理，按輸入順序向f[n]插入所有出現過的數軸坐標，形成f[n]數組。圖中出現Lx、Rx，表示第x個區間的左邊界和右邊界。離散化的第一步完成后，可以看到這個離散化后的新數組有多個相同且無序的值。所以第二步就是對f[n]排序、去重，形成新序列。新序列中所有離散點對“緊挨”在一起了。但這個“緊挨”在一起的數組只是下標，不是實際的值。所以還要創建一個大小跟離散化后的數組f[n]一樣大的數組S[n]用來存放未離散化前的下標值。最后可以通過一個find()函數，找出原下標經過離散化后的新坐標，并賦值。STL函數實現離散化lower_bound()函數的功能是在有序地數列中查找某個元素的相對位置，這個位置正好是做離散化時元素初值對應的新值。lower_bound()返回值是一個迭代器,返回指向大于等于key的第一個值的位置。lower_bound()的對象是有序數組或容器。上程序返回5。將key換成10，所有val都小于key,返回last的位置。輸出8。沒有-a，則輸出返回的指針位置。unique()函數處理去重問題，即把相同的數據離散化為一個數據。unique()包含于<algorithm>頭文件中,功能是將數組中相鄰的重復元素去除。然而其本質是將重復的元素移動到數組的末尾，最后再將迭代器指向第一個重復元素的下標。例題：火燒赤壁曹操平定北方以后，公元208年，率領大軍南下，進攻劉表。他的人馬還沒有到荊州，劉表已經病死。他的兒子劉琮聽到曹軍聲勢浩大，嚇破了膽，先派人求降了。孫權任命周瑜為都督，撥給他三萬水軍，叫他同劉備協力抵抗曹操。隆冬的十一月，天氣突然回暖，刮起了東南風。沒想到東吳船隊離開北岸大約二里距離，前面十條大船突然同時起火。火借風勢，風助火威。十條火船，好比十條火龍一樣，闖進曹軍水寨。那里的船艦，都擠在一起，又躲不開，很快地都燒起來。一眨眼工夫，已經燒成一片火海。曹操氣急敗壞的把你找來，要你鉆入火海把連環線上著火的船只的長度統計出來！題目給定每個起火部分的起點和終點，請你求出燃燒位置的長度之和。輸入第一行一個整數，表示起火的信息條數n。接下來n行，每行兩個整數a,b，表示一個著火位置的起點和終點（注意：左閉右開）。輸出一行一個整數表示答案。數據規模與約定：對于全部的測試點，保證1≤n≤2*10^4，?2^31≤a≤b<2^31，且答案小于2^31。此題為典型的區間修改、區間查詢板子題。可能唯一的問題就是區間過大，即a,b的值為2^31。這個數據范圍直接開樹狀數組或線段樹都不好處理。可以首先考慮小數據量。如果[ai,bi)中ai,bi的值很小，可以考慮用一個數組表示數軸。數組元素fi表示數軸上一個長度為1的區間是否被染色。例如fi=0表示區間[i，i+1]未被染色，反之被染色。接著暴力枚舉每個區間，執行操作即可。但是若ai,bi很大則需要考慮離散化操作。離散化可以在保持原數值之間相對大小關系不變的情況下，將其映射為正整數，即對每個可能用到的數值分配一個編號，用編號來代替數值進行操作。這樣可以將無用數值去除，只保留關鍵數值，達到壓縮時間復雜度的目的。本題數據量過大，無法用一個f數組表示這個數軸，且模擬過程時間復雜度過大。但數軸上兩個相鄰端點，不一定是同一區域的端點，之間的所有點都可以一視同仁地視為同時被染色，或同時不被染色。代碼略。有興趣的朋友可以在網站留言區討論代碼，謝謝。例題：程序自動分析在實現程序自動分析的過程中，常常需要判定一些約束條件是否能被同時滿足。考慮一個約束滿足問題的簡化版本：假設x1,x2,x3,?代表程序中出現的變量，給定n個形如xi=xj或xi!=xj的變量相等/不等的約束條件。請判定是否可以分別為每一個變量賦予恰當的值，使得上述所有約束條件同時被滿足。例如，一個問題中的約束條件為：x1=x2,x2=x3,x3=x4,x4!=x1，這些約束條件顯然是不可能同時被滿足的，因此這個問題應判定為不可被滿足。現在給出一些約束滿足問題，請分別對它們進行判定。輸入的第一行包含一個正整數t，表示需要判定的問題個數。注意這些問題之間是相互獨立的。對于每個問題，包含若干行：第一行包含一個正整數n，表示該問題中需要被滿足的約束條件個數。接下來n行，每行包括三個整數i,j,e，描述一個相等/不等的約束條件，相鄰整數之間用單個空格隔開。若e=1，則該約束條件為xi=xj。若e=0，則該約束條件為xi!=xj。輸出包括t行。輸出文件的第k行輸出一個字符串YES或者NO（字母全部大寫），YES表示輸入中的第k個問題判定為可以被滿足，NO表示不可被滿足。數據范圍：1<=n<=10^5;1<=i,j<=10^9。此題變量之間的關系只有等于和不等于，且等于關系之間不會沖突，不等于關系之間也不會沖突。所以僅考慮等于關系和不等于關系之間的沖突。因此，此題可以用染色法或并查集預處理相等關系，求出所有相等關系連通塊，再檢查所有不等關系，判斷沖突即可。題目的關鍵在于10^9的數據量無法作暴力處理，考慮到總共有10^5個關系，每個關系涉及兩個變量，故只有2*10^5個變量，其余變量可以忽略，所以考慮離散化解決。收集所有變量標號，排序去重，導入c[]數組。用下標i代替標號c[i]。這樣可以使得數量所見到2n以內，問題可解。代碼略。有興趣的朋友可以在網站留言區討論代碼，謝謝。例題:過度種植在一個笛卡爾平面坐標系里（則X軸向右是正方向，Y軸向上是正方向），有N(1<=N<=1000)個矩形，第i個矩形的左上角坐標是(x1,y1),右下角坐標是（x2,y2）。問這N個矩形所覆蓋的面積是多少？注意：被重復覆蓋的區域的面積只算一次。輸入第一行整數N(1<=N<=10001),接下來有N行，每行描述一個矩形的信息，分別是矩形的x1、y1、x2、y2。其中-10^8<=x1,y1,x