文章目錄

• 前言
• 普通平衡樹
• 文藝平衡樹
• 郁悶的出納員
• 書架
• 寵物收養場
• 機械排序
• 千山鳥飛絕
• 總結

前言

專門刷了一天半的平衡樹 （附帶劃水OvO）
使用的是蜜汁常數的splay
感覺對平衡樹的理解還是有幫助的
一些較為常規的平衡樹的題應該是差不多了
更正之前剛學的觀點！
平衡樹當然在維護排名上很有優勢
但它最強大的功能應該是區間問題
還有一些對于整個集合改變的亂七八糟的神奇標記（見：千山鳥飛絕）
一道道說一說吧

普通平衡樹

傳送門
怎么能不水一發模板呢
（連打了三天后終于能二十分鐘打完一次A了qwq）
當然還有一個強化版模板

文藝平衡樹

傳送門
這題我初看根本沒有看出來跟平衡樹有個毛線關系
看了好幾篇題解才明白了思想
就是按數列順序建一棵樹，然后每次把區間內的提到一起打個翻轉標記
標記是精髓 （線段樹頻頻點頭）
注意不要忘了pushdown！（線段樹繼續點頭）

郁悶的出納員

傳送門
這題就好辦不少了
經典的維護排名問題
關鍵是離線處理一個對整體員工工資調整的累加器

書架

傳送門
這個的操作還是比較靈活的
get：不會就提到根試試
放到頂部就是把s提到根后左子樹全接到后繼上
底部反過來同理
與前一本（后一本）交換就直接提到根再與前驅（后繼）交換信息就可以了

寵物收養場

傳送門
比較裸了
這也紫我實在沒話說
題解好多說建兩棵平衡樹
但我覺得減一棵足夠了啊
記錄一下當前是狗多還是人多就行了
愛護環境，節約樹木

機械排序

傳送門
本題的關鍵是相同編號按初始順序選擇
所以預處理出來下一個相同編號的位置就能確定每次要翻轉的東西
再記錄一下這些東西對應的splay樹上的編號
就變成文藝平衡樹了

千山鳥飛絕

傳送門
作為一道畢業題 （xs，根本還畢不了業） 可以說是不錯了
把坐標離散化一下
然后對每個坐標建一課樹
更新對樹里面的用標記，對于根和新加入的直接暴力更新就行
這個不能算自己的蜜汁設定導致我寫出了各種各樣的bug
最后寫的怪東西常數過大，變成了吸氧代碼
開始歸咎于splay的常數

總結

總的來說，我的平衡樹還差得遠呢
但至少可以說會一點了
NOIP就是考平衡樹應該也會裸一點吧（祈禱ing）
繼續加油哇！OvO

總結

以上是生活随笔為你收集整理的平衡树练习总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。