Part 4

由于 SX 设计的数据结构太多了，我会不断更新。

本题单当前设计的内容包括：trie 树，可并堆，可持久化，lct。

提高组数据结构题单

省选题树形数据结构题单1

省选根号数据结构题单

trie

其实最常见的 trie 是 01 trie。

对于 26 位的 trie 一般在字符串题中更为常见。

• P3369 【模板】普通平衡树
• P2922 [USACO08DEC]Secret Message G
• P3065 [USACO12DEC]First! G
• P4735 最大异或和
• P5283 [十二省联考2019]异或粽子
• P3346 [ZJOI2015]诸神眷顾的幻想乡
• P3808 【模板】AC自动机（简单版）
• P3796 【模板】AC自动机（加强版）
• P5357 【模板】AC自动机（二次加强版）

可并堆

常见的可并堆有配并堆，左偏树等。

• P3377 【模板】左偏树（可并堆）

• P2713 罗马游戏

• P1552 [APIO2012]派遣

• P4331 [BalticOI 2004]Sequence 数字序列

• P3261 [JLOI2015]城池攻占

• P3642 [APIO2016]烟火表演

  可持久化

  这儿没有包括主席树和可持久化 trie，这些数据结构也相对小众。

• P3919 【模板】可持久化数组（可持久化线段树/平衡树）

• P3835 【模板】可持久化平衡树

• P5055 【模板】可持久化文艺平衡树

• P3402 可持久化并查集

• P4768 [NOI2018]归程

• P2483 【模板】k短路 / [SDOI2010]魔法猪学院

  LCT

  link cut tree 是基于 splay 的一种动态树。

• P3690 【模板】Link Cut Tree （动态树）

• P3203 [HNOI2010]弹飞绵羊

• P1501 [国家集训队]Tree II

• P2387 [NOI2014]魔法森林

• P2147 [SDOI2008]洞穴勘测

• P4299 首都

• P3703 [SDOI2017]树点涂色

• P4338 [ZJOI2018]历史

1. P3369 - 【模板】普通平衡树
2. P2922 - [USACO08DEC] Secret Message G
3. P3065 - [USACO12DEC] First! G
4. P4735 - 最大异或和
5. P5283 - [十二省联考 2019] 异或粽子
6. P3346 - [ZJOI2015] 诸神眷顾的幻想乡
7. P3808 - AC 自动机（简单版）
8. P3377 - 【模板】可并堆 1
9. P2713 - 罗马游戏
10. P1552 - [APIO2012] 派遣
11. P4331 - [BalticOI 2004] Sequence (Day1)
12. P3261 - [JLOI2015] 城池攻占
13. P3642 - [APIO2016] 烟花表演
14. P3919 - 【模板】可持久化线段树 1（可持久化数组）
15. P3835 - 【模板】可持久化平衡树
16. P5055 - 【模板】可持久化文艺平衡树
17. P3402 - 【模板】可持久化并查集
18. P4768 - [NOI2018] 归程
19. P2483 - 【模板】k 短路 / [SDOI2010] 魔法猪学院
20. P3690 - 【模板】动态树（LCT）
21. P3203 - [HNOI2010] 弹飞绵羊
22. P1501 - [国家集训队] Tree II
23. P2387 - [NOI2014] 魔法森林
24. P2147 - [SDOI2008] 洞穴勘测
25. P4299 - 首都
26. P3703 - [SDOI2017] 树点涂色
27. P4338 - [ZJOI2018] 历史