數據結構題目選講江蘇省淮陰中學張坤有哪些數據結構？數組棧隊列鏈表樹堆有哪些高級數據結構？哈希表優先隊列與二叉堆并查集線段樹樹狀數組平衡樹塊狀鏈表后綴數組樹鏈剖分和動態樹……有哪些NOIP會考的高級數據結構？哈希表優先隊列與二叉堆并查集線段樹樹狀數組平衡樹塊狀鏈表后綴數組樹鏈剖分和動態樹……題目選講例題零NOIP2012借教室在大學期間，經常需要租借教室。大到院系舉辦活動，小到學習小組自習討論，都需要向學校申請借教室。教室的大小功能不同，借教室人的身份不同，借教室的手續也不一樣。面對海量租借教室的信息，我們自然希望編程解決這個問題。我們需要處理接下來n天的借教室信息，其中第i天學校有ri個教室可供租借。共有m份訂單，每份訂單用三個正整數描述，分別為dj,sj,tj，表示某租借者需要從第sj天到第tj天租借教室（包括第sj天和第tj天），每天需要租借dj個教室。例題零NOIP2012借教室我們假定，租借者對教室的大小、地點沒有要求。即對于每份訂單，我們只需要每天提供dj個教室，而它們具體是哪些教室，每天是否是相同的教室則不用考慮。借教室的原則是先到先得，也就是說我們要按照訂單的先后順序依次為每份訂單分配教室。如果在分配的過程中遇到一份訂單無法完全滿足，則需要停止教室的分配，通知當前申請人修改訂單。這里的無法滿足指從第sj天到第tj天中有至少一天剩余的教室數量不足dj個。現在我們需要知道，是否會有訂單無法完全滿足。如果有，需要通知哪一個申請人修改訂單。例題零NOIP2012借教室輸入文件為classroom.in。第一行包含兩個正整數n,m，表示天數和訂單的數量。第二行包含n個正整數，其中第i個數為ri，表示第i天可用于租借的教室數量。接下來有m行，每行包含三個正整數dj,sj,tj，表示租借的數量，租借開始、結束分別在第幾天。每行相鄰的兩個數之間均用一個空格隔開。天數與訂單均用從1開始的整數編號。例題零NOIP2012借教室輸出文件為classroom.out。如果所有訂單均可滿足，則輸出只有一行，包含一個整數0。否則（訂單無法完全滿足）輸出兩行，第一行輸出一個負整數-1，第二行輸出需要修改訂單的申請人編號。例題零NOIP2012借教室輸入432543213324424輸出-12對于10%的數據，有1≤n,m≤10；對于30%的數據，有1≤n,m≤1000；對于70%的數據，有1≤n,m≤10^5；對于100%的數據，有1≤n,m≤10^6,0≤ri,dj≤10^9,1≤sj≤tj≤n。例題零NOIP2012借教室此題就是一個線段樹裸題，但100萬的數據比較大。線段樹的做法？例題零NOIP2012借教室此題就是一個線段樹裸題，但100萬的數據比較大，線段樹也許會承受不了。而最終結果表明，由于鑒于CCF的評測機，線段樹只能拿到90，所以，我們不得不另尋他法。例題零NOIP2012借教室這道題的數據范圍比較大，因此必須要考慮對數級及一下的算法。本題的實質是找到第一組不能滿足要求的申請，因此可以考慮用二分法。設初始左端點為1，右端點為n，在二分的過程中，每次判斷的是從第一組申請到當前區間中點這一組申請是否全部都能被滿足。如果這一段申請都能滿足，則左端點下移否則右端點上移。最后得到的長度為1的區間就是答案。另外，可能要特判一下答案是n的情況。（根據程序寫法不同決定是否需要特判……）例題零NOIP2012借教室

在判斷申請的時候，需要使用差分數組來計算申請的數量。差分數組用于記錄原數值數組中相鄰兩個數的差值。（以下為與前面的數的差值）。在對于從l到r的數值為num的操作中，將l的數值增加num，r+1的數值減少num即可。最后對差分數組求前綴和即可得到每天教室的數量。差分數組的sumi對應原數組第i個元素的數值。例題的啟示數據結構題的解法往往不止一種。往往我們可以使用時間分治優化一維，減少編程復雜度和常數。例題一NOI2001食物鏈

動物王國中有三類動物A,B,C，這三類動物的食物鏈構成了有趣的環形。A吃B，B吃C，C吃A。現有N個動物，以1－N編號。每個動物都是A,B,C中的一種，但是我們并不知道它到底是哪一種。有人用兩種說法對這N個動物所構成的食物鏈關系進行描述：第一種說法是“1XY”，表示X和Y是同類。第二種說法是“2XY”，表示X吃Y。例題一NOI2001食物鏈此人對N個動物，用上述兩種說法，一句接一句地說出K句話，這K句話有的是真的，有的是假的。當一句話滿足下列三條之一時，這句話就是假話，否則就是真話。1）當前的話與前面的某些真的話沖突，就是假話；2）當前的話中X或Y比N大，就是假話；3）當前的話表示X吃X，就是假話。你的任務是根據給定的N（1<=N<=50,000）和K句話（0<=K<=100,000），輸出假話的總數。輸入格式第一行是兩個整數N和K，以一個空格分隔。以下K行每行是三個正整數D，X，Y，兩數之間用一個空格隔開，其中D表示說法的種類。若D=1，則表示X和Y是同類。若D=2，則表示X吃Y。輸出格式只有一個整數，表示假話的數目。樣例輸入100711011212223233113231155樣例輸出3例題一NOI2001食物鏈自由討論如果

動物王國中只有兩類動物A,B，這兩類動物的食物鏈構成了有趣的環形。A吃B，B吃A……如果

動物王國中只有兩類動物A,B，這兩類動物的食物鏈構成了有趣的環形。A吃B，B吃A……這是一個二分圖那么是不是可以對這些動物進行染色，令顏色相同的為一類。但當你遇到一個沒有染過色的動物，你需要給它染什么顏色呢？而且這好像是圖論的內容與數據結構選講無關一些想法如果A吃B，B吃C，C吃D，……F→E→D→C→B→A那么A和D是同類，他們也是捕食關系，矛盾？同類的意義F→E→D→C→B→AA和D的距離為3模3意義下相等啟發圖可以變為樹關系可以用距離表示，模3意義下加加減減想到了什么并查集！具體步驟用father[n],path[n]數組分別記錄當前結點的祖先和到祖先的距離。這里規定距離為0時為同類，為1時表示被祖先吃，為2時表示吃祖先。初始時每個元素的祖先是自己，距離為0。

對于每一句話，首先判斷是x,y是否大于n，是否出現自己吃自己的情況，滿足時討論如下兩種情況：如果d=1，表示讀入的x和y是同類，這時分別找到x,y和祖先fx,fy，如果fx=fy，說明他們是同一祖先。這時判斷x和y到祖先的距離是否相等，顯然，不相等證明這是一句假話。如果fx<>fy，說明x和y不在同一集合中，此時將這兩個集合合并。合并時可以通過一個簡單的向量關系算出fx->fy的距離，即path[fx]=path[y]-path[x].

對于每一句話，首先判斷是x,y是否大于n，是否出現自己吃自己的情況，滿足時討論如下兩種情況：如果d=2，表示x吃y，同樣的找到它們的祖先，若fx=fy，則根據向量關系判斷它們的距離是否矛盾，即檢查path[x]-path[y]-2是否為0。若fx<>fy，則類似地根據已有的向量關系算出fx->fy的距離，即path[fx]=path[y]-path[x]+2.注意的地方是，因為path在運算過程可能出現負數，為避免這一情況且保證path的性質，可以在每次對path運算后加三再對三取模。int

Fa[maxn],Dis[maxn];int

Find(intx){

if(x==Fa[x])returnx;

inty=Find(Fa[x]);

Dis[x]+=Dis[Fa[x]];returnFa[x]=y;}例題二InputOutputSampleInputSampleOutput12例題二自由討論一些想法共三維x,y,cc很小對c暴力處理，好像可以接受一些想法如何對某個顏色快速維護子矩陣中該顏色的數量可選擇的數據結構四分樹二維線段樹二維樹狀數組各種數據結構的優勢和劣勢兼顧編程復雜度和運行效率例題三Input輸入共兩行，第一行為一個整數N，N表示物品的個數，1<=N<=100000。第二行為N個用空格隔開的正整數，表示N個物品最初排列的編號。Output輸出共一行，N個用空格隔開的正整數P1,P2,P3…Pn，Pi表示第i次操作前第i小的物品所在的位置。注意：如果第i次操作前，第i小的物品己經在正確的位置Pi上，我們將區間[Pi,Pi]反轉(單個物品)。SampleInput6345162SampleOutput464566自由討論要求支持區間最小值查詢，區間翻轉的數據結構如果沒有翻轉……支持翻轉的數據結構塊狀鏈表——時間效率√n平衡樹做法無與倫比的splay和spaly歡迎用作模版題Picks博士觀察完金星凌日后，設計了一個復雜的電阻器。為了簡化題目，題目中的常數與現實世界有所不同。這個電阻器內有編號為1～n的n個獨立水箱，水箱呈圓柱形，底面積為1m2，每個水箱在頂部和底部各有一個閥門，可以讓水以1m3/s的流量通過，每個水箱的上閥門接水龍頭，可以無限供應水，下閥門不接東西，可以讓水流出。水箱頂部和底部都有一個接口，水的電阻率為1Ω?m。水箱的高度足夠高，有一個導電浮標浮在水面上，通過導線與水箱頂的接口相連。一開始時第ii個水箱中有aim3的水。例題四Picks博士接下來就需要對這個復雜的電阻器進行調試。他會進行以下五種操作。1、打開編號在[l,r]中的所有水箱的上方閥門x秒，然后關上它們的上方閥門。2、打開編號在[l,r]中的所有水箱的下方閥門x秒，然后關上它們的下方閥門。3、將編號在[l,r]中的所有水箱的下方閥門與大海通過連通器以一定方式相連，使得這些水箱中都恰擁有xm3的水，然后關上它們的下方閥門，撤去連通器。4、在第y個水箱的上下方接口處接上一個電動勢為1V的電源，電源沒有內阻，Picks博士會測量出通過電源的電流大小，之后撤去該電源。5、由于水浸泡過的地方會留下明顯的水漬而沒有被水浸泡過的地方不會有，Picks博士可以據此測量出此時第y個水箱的水漬高度，以推斷曾經最多有多少水，節約他的建造成本。現在，他請你來幫他做預實驗，你能告訴他每次測量得到的電流大小以及測量得到的最多的水量是多少嗎？例題四輸入格式第一行兩個數：n,m。接下來一行n個數，第i個數表示初始時第i個水箱內有aim3的水。接下來m行中，第i行第一個數ti表示操作類型：若ti=1，則接下來三個整數li,ri,xi表示打開編號在[li,ri]中的所有水箱的上方接口xi秒。若ti=2，則接下來三個整數li,ri,xi表示打開編號在[li,ri]中的所有水箱的下方接口xi秒。若ti=3，則接下來三個整數li,ri,xi表示將編號在[li,ri]中的所有水箱與大海連接，使這些水箱中都恰有xim3的水。若ti=4，則接下來一個整數yi，表示測量在第yi個水箱的上下方接口處接上一個電動勢為1V的電源時通過電源的電流。若ti=5，則接下來一個整數yi，表示測量此時在第yi個水箱中的水漬高度。輸出格式對于每個ti=4，輸出一個整數表示通過電源的電流大小的倒數（單位為A?1），如果電流為無窮大則輸出0。對于每個ti=5，輸出一個整數表示在第yi個水箱中的水漬高度（單位為m）。樣例輸入一5612345213241114153315442樣例輸出一034自由討論一些想法操作三可以被操作一和操作二取代如何做題目要義請你寫一個數據結構支持以下功能：1：區間[l,r]加x2：區間[l,r]減x并和0取max3：區間值修改為x4：單點詢問5：單點歷史最大值詢問如何拿到部分分做法線段樹維護分段函數標記就是一個二元組(a,b)表示標記生效后x=max(x+a,b)1操作就是打(x,0)的標記2就是(-x,0)3就是(-inf,v)做法標記是滿足結合律和封閉性的然后兩個標記怎么合并呢？g(f(x))=max(x+max(fa+ga,-inf),max(fb+ga,gb))（打f標記的時間在前，打g標記在后）中間和-inf取max是為了不使多個-inf加爆了做法對于歷史最大值，我們要記錄的是歷史最大標記而不是直接在每個點記錄歷史最大值為什么是這樣的？假設我們進行一次區間賦為inf的操作，接著有全部賦為0，標記還沒來得及下傳更新歷史最大值就被后一個標記cha了所以每個點記錄歷史最大值是錯的更簡單的做法……再觀察題目請你寫一個數據結構支持以下功能：1：區間[l,r]加x2：區間[l,r]減x并和0取max3：區間值修改為x4：單點詢問5：單點歷史最大值詢問再觀察題目如何簡化操作函數？再觀察題目如何簡化操作函數？用一個數組序列表示。再觀察題目請你寫一個數據結構支持以下功能：1：區間[l,r]加x表示為+x2：區間[l,r]減x并和0取max表示為-x3：區間值修改為x表示為-inf+x舉例5612345213241114153315442對于第3位而言3-2+1-inf+4性質？性質目前的水位是包含右端點的和最大的一個子序列歷史最高的水位是和最大的一個子序列證明？性質目前的水位是包含右端點的和最大的一個子序列歷史最高的水位是和最大的一個子序列線段樹維護即可。問題描述:一個無向樹的度數為2的結點稱為假結點，其它結點稱為真結點。一個無向樹的簡化樹其結點由原樹的全體真結點組成，兩個真結點之間有邊當且僅當它們在原樹中有邊，或者在原樹中有一條聯結這兩個結點的路，其中間節點全是假結點。兩個無向樹各自的簡化樹如果同構，即存在結點之間的一一對應，使得在一個樹中的任意兩個結點之間有邊當且僅當它們的對應結點在另一個樹中有邊，則稱原來的兩個無向樹實質同構。給定若干個無向樹，將相互實質同構的無向樹只保留一個其余刪除。統計剩下的相互不實質同構的無向樹個數，并將它們的簡化樹結點個數從小到大輸出。例題五輸入格式:第一行只有一個正整數m,后面依次輸入m個無向樹，每個無向樹先用一行輸入結點個數n，結點就用1到n表示，然后用n-1行輸入n-1條無向邊，每行有兩個1到n之間的不同的正整數，用一個空格隔開，代表這兩個結點之間有無向邊。兩個樹之間無空行。輸出格式:

第一行輸出一個正整數，即輸入中不計實質同構包含無向樹的個數m0(1<=m0<=m)。第二行包含不嚴格遞增的m0個正整數，表示這m0個無向樹的簡化樹結點個數。相鄰兩數用一個空格隔開。例題五樣例輸入24142434513233445樣例輸出14例題五30%的數據滿足2<=m<=10，2<=n<=1060%的數據滿足：2<=