清北學(xué)堂2012國慶NOIP課件——模型構(gòu)建與全面分析2.pptx

1、高級(jí)數(shù)據(jù)結(jié)構(gòu),汪一寧 清華大學(xué),基本數(shù)據(jù)結(jié)構(gòu),易于實(shí)現(xiàn) 功能簡單，效率一般 優(yōu)先考慮使用簡單數(shù)據(jù)結(jié)構(gòu)來完成一道試題。,星際爭霸 （經(jīng)典試題）,給出一個(gè)無向圖，有N個(gè)點(diǎn)M條邊，N, M = 100,000 支持兩種操作 刪除圖中的一條邊 詢問兩個(gè)頂點(diǎn)是否可達(dá) 操作總數(shù)=100,000,知識(shí)準(zhǔn)備：并查集,維護(hù)分離集合的合并與查詢 時(shí)間復(fù)雜度 合并和查詢兩個(gè)集合：O(alpha(n) 注意事項(xiàng) 按秩合并 路徑壓縮,解題思路,并查集并不支持分離集合的操作 解決方案：逆向思維！,1009 of Tianjin Online Contest, 2012,一個(gè)序列有一個(gè)左指針和一個(gè)右指針，要求維護(hù)以下操作

2、將某個(gè)指針向左或者向右移動(dòng) 在某個(gè)指針的左側(cè)或者右側(cè)插入一個(gè)元素 在某個(gè)指針的左側(cè)或者右側(cè)刪除一個(gè)元素 將兩個(gè)指針之間的元素反轉(zhuǎn),解題思路,使用最簡單的方法解決問題 思考：所有的操作都和兩個(gè)指針的位置相關(guān)。,合理使用STL庫,STL庫中的重要容器 Vector, Queue, Deque, Stack, Priority Queue Map, Set, Multimap, Multiset,線段樹,線段樹結(jié)構(gòu) 為區(qū)間1, n中的每個(gè)元素分配一個(gè)葉節(jié)點(diǎn) 針對(duì)相鄰的兩個(gè)節(jié)點(diǎn)，產(chǎn)生一個(gè)上層節(jié)點(diǎn) 如此做直到某一層只有一個(gè)包含整個(gè)區(qū)間的節(jié)點(diǎn)為止。,線段樹：建樹過程,BuildTree(p, b, e):

3、 Create a new node N If b 1); N.right = BuildTree(p1)+1, e),線段樹：節(jié)點(diǎn)數(shù)據(jù)記錄,某一個(gè)節(jié)點(diǎn)代表一個(gè)區(qū)間(b, e)上的數(shù)據(jù)記錄。如果b=e，則這個(gè)點(diǎn)是葉子結(jié)點(diǎn)；否則，這個(gè)點(diǎn)有且僅有兩個(gè)孩子。 節(jié)點(diǎn)數(shù)據(jù) 向上更新型，例如區(qū)間上所有元素的和，最小值，等等 向下更新型，例如該區(qū)間是否被反轉(zhuǎn)，,線段樹：訪問機(jī)制,Visit(p, b, e): Update Downward If b = p.b and e = p.e: do the visit Else: If b = p.right.b: Visit(p1)+1, MAX(b, p.l

4、eft.b), e) Update Upward,線段樹：適用范圍,一個(gè)區(qū)間上的統(tǒng)計(jì)信息可以通過其兩個(gè)子區(qū)間上的信息合并得到。 對(duì)一個(gè)區(qū)間上所有元素的操作可以分解成對(duì)其兩個(gè)子區(qū)間上元素分別的操作。,回顧前述試題,修改 不允許插入或者刪除元素，但是可以修改任何一個(gè)位置的元素 可以將任何一段區(qū)間中的元素反轉(zhuǎn) 要求查詢?nèi)魏我欢螀^(qū)間中元素的和 思考 哪些數(shù)據(jù)需要“向上”維護(hù)？ 哪些數(shù)據(jù)需要“向下”維護(hù)？,USACO hotel,有N間房間空著，M頭奶牛前來入住 每一頭奶牛希望訂到連續(xù)d間房間 如果沒有這樣的連續(xù)d間房間，這頭奶牛放棄入住 否則，分配編號(hào)最小的滿足條件的連續(xù)d間房間給這頭奶牛 N, M

5、= 50,000,解題思路,哪些向上更新的數(shù)據(jù)需要被維護(hù)？ 區(qū)間中空閑房間總數(shù)？ 哪些向下更新的數(shù)據(jù)需要被維護(hù)？ 該區(qū)間是否全部被預(yù)訂 怎樣才能夠找出連續(xù)的d間空閑房間？ 區(qū)間左端空閑房間數(shù) 區(qū)間右端空閑房間數(shù),彩球統(tǒng)計(jì) （原創(chuàng)）,有N個(gè)彩球排成一列，每個(gè)球的顏色是1M中的一種。 有Q次詢問，每次詢問一個(gè)區(qū)間a,b中有多少種不同顏色的球 N, M, Q = 100,000,解題思路,線段樹能夠維護(hù)“區(qū)間中的顏色數(shù)目”這一數(shù)據(jù)么？,解題思路 (contd),離線詢問試題 將詢問區(qū)間按照左端點(diǎn)排序 只維護(hù)每種顏色的第一個(gè)球 先用鏈表把每一種顏色的球串起來。 隨著詢問區(qū)間向右移動(dòng)，在鏈表上移動(dòng)指針。

6、 使用線段樹來回答詢問區(qū)間中有多少個(gè)每種顏色的第一個(gè)球,平衡樹,二叉搜索樹 一顆中序遍歷是升序的二叉樹 平衡二叉樹 采用某種機(jī)制控制二叉樹的高度 嚴(yán)格平衡：AVL, 紅黑樹，SBT 均攤平衡：Splay 期望平衡：Treap 關(guān)鍵操作旋轉(zhuǎn),Treap介紹,每個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)隨機(jī)的“優(yōu)先值” 結(jié)構(gòu)：鍵值構(gòu)成二叉搜索樹，優(yōu)先值構(gòu)成堆 優(yōu)勢(shì)： 旋轉(zhuǎn)方式只有兩種，插入刪除簡單 劣勢(shì)： 需要多維護(hù)一個(gè)數(shù)據(jù) 常數(shù)較其他平衡樹大,Splay介紹,核心思想：任何操作之后（或之前），將一個(gè)節(jié)點(diǎn)旋轉(zhuǎn)至根節(jié)點(diǎn)。 優(yōu)勢(shì)： 思想簡單，容易掌握 可以實(shí)現(xiàn)一些特殊的統(tǒng)計(jì)功能 劣勢(shì)： 4種旋轉(zhuǎn)，略麻煩 僅保證均攤時(shí)間復(fù)雜度，一次操作可能耗時(shí)很長，樹結(jié)構(gòu)也可能很不好。,數(shù)列維