數(shù)據(jù)結(jié)構(gòu)

two permutation

平衡樹維護(hù)哈希值

合并

啟發(fā)式合并

適合只有合并沒有拆分的問題

樹鏈剖分

左偏樹

fhq_treap合并

滿足一顆子樹內(nèi)的所有節(jié)點(diǎn)都小于另一顆子樹

排布石頭

平衡樹啟發(fā)式合并

樹上啟發(fā)式合并

樹上的子樹問題，比如樹上眾數(shù)問題
全局維護(hù)數(shù)據(jù)結(jié)構(gòu)，可以不好合并，但是只需要單點(diǎn)插入單點(diǎn)刪除即可。

CCPC Final 2019 K

對樹上每個(gè)點(diǎn)維護(hù)子樹內(nèi)所有點(diǎn)編號構(gòu)成的連續(xù)段個(gè)數(shù)

笛卡爾樹

滿足堆性質(zhì)的二叉樹，中序遍歷為原序列，每個(gè)點(diǎn)為其子樹的最值，常用來處理區(qū)間最值相關(guān)問題。反映了大小關(guān)系的層次結(jié)構(gòu)。

O(n)建樹

維護(hù)單調(diào)棧維護(hù)右鏈，相當(dāng)于對原序列維護(hù)一個(gè)單調(diào)棧中的所有元素

Special Segments Of Permutation

查詢有多少區(qū)間，滿足端點(diǎn)處的數(shù)之和等于區(qū)間最大值
區(qū)間最大值等于區(qū)間端點(diǎn)的lca

可以轉(zhuǎn)化為樹上問題，利用樹上啟發(fā)式合并解決，然后因?yàn)橐还仓挥袃蓚€(gè)兒子，然后需要處理出一個(gè)兒子的桶，然后dfs另一個(gè)兒子，所以我們每次啟發(fā)式合并，每次繼承重兒子的桶，然后暴力搜索輕兒子。

線段樹合并

雨天的尾巴

有一顆樹，第i次操作將樹上路徑的每一個(gè)點(diǎn)放一個(gè)i，最終對每個(gè)點(diǎn)求其中出現(xiàn)次數(shù)最多的數(shù)。顯然需要數(shù)據(jù)結(jié)構(gòu)維護(hù)，然后是一個(gè)離線問題，并且是一個(gè)樹上問題，所以我們就可以使用線段樹合并解決這個(gè)問題了。

線段樹優(yōu)化建圖

利用線段樹可以把一個(gè)區(qū)間拆分為log個(gè)節(jié)點(diǎn)的性質(zhì)。

一個(gè)點(diǎn)向一個(gè)區(qū)間內(nèi)的所有點(diǎn)連邊

一個(gè)區(qū)間內(nèi)所有點(diǎn)到一個(gè)點(diǎn)連邊

區(qū)間內(nèi)所有點(diǎn)到另一個(gè)區(qū)間連邊，可以利用一個(gè)中間點(diǎn)轉(zhuǎn)化為1和2

可持久化

可以處理線性的問題或者樹形的問題

回家

n個(gè)點(diǎn)m條邊的有向圖，每條邊的權(quán)值是2^li，求s到t的最短路輸出答案對998244353取模的結(jié)果。

只需要用可持久化線段樹維護(hù)二進(jìn)制，然后加數(shù)可以快速維護(hù)，只需要修改log個(gè)線段樹節(jié)點(diǎn)，然后還需要維護(hù)一下哈希值，就可以快速查詢lcp就可以O(shè)(logn)比較兩個(gè)數(shù)的大小。

可持久化并查集

？？？

離線加強(qiáng)版

假的可持久化，版本之間構(gòu)成了一個(gè)版本樹，每個(gè)版本由自上而下的操作構(gòu)成，如果在全局維護(hù)可支持棧序撤銷的數(shù)據(jù)結(jié)構(gòu)那么對版本樹離線dfs即可。

序列分塊

二維數(shù)點(diǎn)

強(qiáng)制在線，求一個(gè)矩形內(nèi)的點(diǎn)的權(quán)值和，帶修改

分塊

外側(cè)對x進(jìn)行排序，然后在塊內(nèi)部對y進(jìn)行排序。然后查詢的時(shí)候整塊可以進(jìn)行二分，零散點(diǎn)暴力。然后修改就可以進(jìn)行

2020CCPC黑龍江省賽 I.Inkball FX

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的数据结构复习的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。