如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題(已修改)
2024-08-04 20:59 本頁面
【正文】 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 廣東省中山市第一中學(xué) 余江偉 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 【 引言 】 ? 在信息學(xué)競賽中，統(tǒng)計(jì)問題十分常見。請(qǐng)看一個(gè)例子： ? 在長度為 N (2≤N≤106)的序列上進(jìn)行 M次以下操作： 查詢第 i項(xiàng)到第 j項(xiàng)的最大值和最小值 Query (i, j) 詢問 第 i項(xiàng)到第 j項(xiàng)的值同時(shí)加上 c Increase (i, j, c) 增加 說明 操作 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 【 引言 】 ? 利用線段樹，可以輕松設(shè)計(jì)出時(shí)間復(fù)雜度O(MlogN)、空間復(fù)雜度 O(N) 的算法。 ? 詳見 2022年薛矛前輩的論文 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 【 引言 】 ? 線段樹在本題取得成功的原因 ? 高效的組織結(jié)構(gòu) ? 很好地支持區(qū)間操作 ? 前提條件 —— 本題中，序列項(xiàng)與項(xiàng)之間隱含著嚴(yán)格不變的次序關(guān)系 ? 當(dāng)統(tǒng)計(jì)對(duì)象次序發(fā)生大規(guī)模變化，線段樹就顯得力不從心了，必須尋找更優(yōu)秀的解法 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 【 例一 】 維護(hù)序列 (NOI2022) ? 寫一個(gè)程序維護(hù)一個(gè)序列，支持 6種操作： ? INSERT a {} ? 在序列第 a 項(xiàng)后插入長度為 n 序列 ? DELETE a b ? 刪除序列的第 a 項(xiàng)到第 b 項(xiàng) ? MAKESAME a b c ? 把序列的第 a 項(xiàng)到第 b 項(xiàng)的值統(tǒng)一改為 c ? REVERSE a b ? 把序列的第 a 項(xiàng)到第 b 項(xiàng)首尾翻轉(zhuǎn)后放回原位 ? GETSUM a b ? 輸出序列的第 a 項(xiàng)到第 b 項(xiàng)的和 ? MAXSUM ? 求序列中和最大的一段非空子列，并輸出最大和 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 【 例一 】 維護(hù)序列 (NOI2022) ? 寫一個(gè)程序維護(hù)一個(gè)序列 ? INSERT a {ck} ? DELETE a b ? MAKESAME a b c ? REVERSE a b ? GETSUM a b ? MAXSUM ? 任何時(shí)刻序列 長度 1 ≤ N ≤ 500,000 ? 操作總數(shù) 1 ≤ M ≤ 20,000 ? 插入數(shù)的總數(shù) 1 ≤ K ≤ 4,000,000 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 【 例一 】 維護(hù)序列 (NOI2022) ? 初步分析 ? 本題需要模擬一個(gè)序列的變化過程并隨時(shí)統(tǒng)計(jì)相關(guān)求和信息 ? 具有操作種類多、規(guī)模大的特點(diǎn) ? 樸素算法 ? 數(shù)組 /鏈表模擬，只能拿到部分分?jǐn)?shù) ? 更優(yōu)秀的算法 ? 塊狀鏈表（參考解答） ，綜合數(shù)組、鏈表的優(yōu)勢(shì) ? 樹形結(jié)構(gòu) 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 【 例一 】 維護(hù)序列 (NOI2022) ? 關(guān)鍵問題 —— 表示 amp。操作 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 【 例一 】 維護(hù)序列 (NOI2022) ? 關(guān)鍵問題 —— 表示 amp。操作 ? 如何表示 ? 二叉查找樹 (BST)表示序列 ? 每個(gè)節(jié)點(diǎn)記錄一個(gè)數(shù) ? BST中序遍歷結(jié)果為原序列 一棵表示 (5,2,1,1,6,7,8,10,5,19,0,21,22,3,4)的 BST 8 6 19 5 2 7 1 1 10 5 22 4 3 21 0 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 【 例一 】 維護(hù)序列 (NOI2022) ? 關(guān)鍵問題 —— 表示 amp。操作 ? 如何操作 ? 不難發(fā)現(xiàn)，大多數(shù)操作都是圍繞某個(gè)“連續(xù)段”進(jìn)行的 ? “連續(xù)段”在 BST中可能比較分散，我們希望把這些節(jié)點(diǎn)聚集起來 ? 伸展樹 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 【 例一 】 伸展樹簡介 ? 伸展樹是一種自適應(yīng) (SelfAdjusting)的 BST。具體地說，每次訪問一個(gè)節(jié)點(diǎn)后，按照一定規(guī)則進(jìn)行旋轉(zhuǎn)，將其調(diào)整為樹的根。 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 【 例一 】 伸展樹簡介 ? 伸展樹是一種自適應(yīng) (SelfAdjusting)的 BST。具體地說，每次訪問一個(gè)節(jié)點(diǎn)后，按照一定規(guī)則進(jìn)行旋轉(zhuǎn)，將其調(diào)整為樹的根。 ? 伸展樹的旋轉(zhuǎn)規(guī)則 ? Zig/Zag ? ZigZig/ZagZag ? ZigZag/ZagZig 如何解決好
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1