【数据结构】高级数据结构-1

本题单主要包含一些高级数据结构的常见套路题目，涉及到不少数据结构，有很简单的题也有难一些的题，建议先充分掌握线段树、平衡树等基础的数据结构知识点后再来练习这些数据结构。 注意，本题单重在介绍一些套路，所以有些比较经典的题目，那么有一些洛谷上没有的经典套路题提供了对应 OJ 的链接。 主要包含的数据结构知识点： ------ ### 一、线段树合并&分裂 线段树分裂通常用于节选序列中的区间或可重集中的值域等，可以解决一些此类的问题。 线段树合并的应用则更加广泛，常见的树上的线段树合并优化 DP 或计数，也有一些套路，如维护后缀树上结点的 endpos 集合。 ------ [P5494 【模板】线段树分裂](https://www.luogu.com.cn/problem/P5494)（练习线段树分裂和合并的模板题） [P2824 [HEOI2016/TJOI2016] 排序](https://www.luogu.com.cn/problem/P2824)（线段树分裂解决区间排序的问题，也可以用二分+线段树解决） [P5298 [PKUWC2018] Minimax](https://www.luogu.com.cn/problem/P5298)（树上问题的线段树合并，这题的标记处理比较特殊） [P4770 [NOI2018] 你的名字](https://www.luogu.com.cn/problem/P4770)（线段树合并维护 SAM 上 endpos 的套路） [P3224 [HNOI2012] 永无乡](https://www.luogu.com.cn/problem/P3224)（线段树合并维护连通块信息，也可以练习离散化映射后线段树直接维护的套路） ------ ### 二、主席树&可持久化 Trie 主席树是在省选难度比赛中应用最为广泛的数据结构之一，而部分功能也可以用可持久化 Trie 代替，好写一些。 然而实际应用中解决普通值域问题多用主席树，而处理异或问题会用可持久化 Trie（事实上权值线段树也可以解决异或问题，但是复杂度稍大，也有题目涉及）。 ------ [P3834 【模板】可持久化线段树 1](https://www.luogu.com.cn/problem/P3834)（主席树/可持久化 01Trie 模板题） [P4735 最大异或和](https://www.luogu.com.cn/problem/P4735)（可持久化 01Trie 解决异或问题模板题） [P2617 Dynamic Rankings](https://www.luogu.com.cn/problem/P2617)（权值线段树的简单扩展——树状数组套权值线段树维护待修改二维数点） [P2633 Count on a tree](https://www.luogu.com.cn/problem/P2633)（树上主席树套路） [P2839 [国家集训队] middle](https://www.luogu.com.cn/problem/P2839)（二分+主席树好题，启发了主席树在值域上建区间的套路） [P5284 [十二省联考2019] 字符串问题](https://www.luogu.com.cn/problem/P5284)（SA/SAM+线段树优化建图，需要可持久化） [P4094 [HEOI2016/TJOI2016] 字符串](https://www.luogu.com.cn/problem/P4094)（二分+主席树好题，主席树求两区间交的套路） [P6071 [MdOI2020] Treequery](https://www.luogu.com.cn/problem/P6071)（~~我 吹 我 自 己~~，主席树与虚树理论结合，也有不太优美的倍增+主席树做法） [P3899 [湖南集训] 更为厉害](https://www.luogu.com.cn/problem/P3899)（启发了主席树能解决的一大类问题——二维数点） [P4197 Peaks](https://www.luogu.com.cn/problem/P4197)（主席树与 Kruskal 重构树的直接结合，也有并查集的做法） [P4175 [CTSC2008] 网络管理](https://www.luogu.com.cn/problem/P4175)（毒瘤的树上线段树套线段树，可以思考套的顺序对应套路） [P3293 [SCOI2016] 美味](https://www.luogu.com.cn/problem/P3293)（主席树处理平移后的异或问题） [P5283 [十二省联考2019] 异或粽子](https://www.luogu.com.cn/problem/P5283)（可持久化 Trie 入门题，可以思考 k 较大的情况） 加强版：[CF241B Friends](https://www.luogu.com.cn/problem/CF241B) [P5795 [THUSC2015] 异或运算](https://www.luogu.com.cn/problem/P5795)（与前一题异曲同工，在一堆可持久化 Trie 上同时做二分） 补充题：[UOJ 266 [清华集训2016] Alice和Bob又在玩游戏](http://uoj.ac/problem/266)（Trie 的全局异或标记，Trie 树合并，非常重要的技巧） ------ ### 三、动态树（LCT） 动态树是处理树的变化和图的变化的有力工具，也有不少扩展与其他数据结构的结合。 这里介绍了一些最基本的动态树技巧。 ------ [P3690 【模板】Link Cut Tree](https://www.luogu.com.cn/problem/P3690)（动态树模板题） [P4219 [BJOI2014] 大融合](https://www.luogu.com.cn/problem/P4219)（LCT 维护子树信息，也可用更高级的 top tree 解决） [P2387 [NOI2014] 魔法森林](https://www.luogu.com.cn/problem/P2387)（LCT 维护加边最小生成树） [P5385 [Cnoi2019] 须臾幻境](https://www.luogu.com.cn/problem/P5385)（LCT 与主席树维护区间连通块，这种数连通块的方法已经成为套路） 补充题：[UOJ 207 共价大爷游长沙](http://uoj.ac/problem/207)（LCT+随机化，这种对于子集的 hash 方法也是套路） ------ ### 四、线性基 线性基是处理子集异或的一种常用工具，在图论上更是有着常见的套路。 ------ [P3812 【模板】线性基](https://www.luogu.com.cn/problem/P3812)（线性基模板） [P4151 [WC2011] 最大XOR和路径](https://www.luogu.com.cn/problem/P4151)（处理路径问题的最常见的套路） [P4570 [BJWC2011] 元素](https://www.luogu.com.cn/problem/P4570)（在线性基上贪心的策略） [P3292 [SCOI2016] 幸运数字](https://www.luogu.com.cn/problem/P3292)（线性基合并的套路，这题还需要点分治或树链剖分） [CF1299D Around the World](https://www.luogu.com.cn/problem/CF1299D)（线性基的综合题，用到一些数学技巧和 DP 技巧） 补充题：[HDU 6579 Operation](http://acm.hdu.edu.cn/showproblem.php?pid=6579)（区间线性基，非常重要的套路） ------ ### 五、动态 DP/全局平衡二叉树 动态 DP 偏数据结构更多，用一个矩阵维护每一次转移的方程，用线段树或平衡树维护矩阵的连乘积，实现快速的计算和修改。 ------ [P4751 【模板】"动态DP"&动态树分治](https://www.luogu.com.cn/problem/P4751)（树上动态 DP 和全局平衡二叉树模板） [SP1716 GSS3 - Can you answer these queries III](https://www.luogu.com.cn/problem/SP1716)（序列动态 DP 模板） [P6021 洪水](https://www.luogu.com.cn/problem/P6021)（另一个树上动态 DP 题，可以用树链剖分练习） [P5024 保卫王国](https://www.luogu.com.cn/problem/P5024)（NOIP 真题，很裸，实在不会一些不太裸的动态 DP） ------ ### 六、CDQ 分治/二维数点模型 cdq 分治是一种重要的分治思路，例如归并排序求逆序对就是 cdq 分治的思想。 二维数点即在给定的二维区间中对点进行统计，可以用 cdq 分治或主席树来实现，待修的则有对应的 cdq 套 cdq，cdq 套树，以及树套树的做法。 ------ [P3810 【模板】三维偏序（陌上花开）](https://www.luogu.com.cn/problem/P3810)（三维偏序模板，可用 cdq 套树状数组或 cdq 套 cdq） [P5621 [DbOI2019] 德丽莎世界第一可爱](https://www.luogu.com.cn/problem/P5621)（四维偏序模板，可用 cdq 套 cdq 套树状数组或 cdq 套树状数组套线段树等解决） [P5445 [APIO2019] 路灯](https://www.luogu.com.cn/problem/P5445)（区间修改的二维数点，注意差分可以让你直接用树状数组套权值线段树维护） [P5044 [IOI2018] meetings 会议](https://www.luogu.com.cn/problem/P5044)（笛卡尔树上的 DP，用线段树优化） [P4899 [IOI2018] werewolf 狼人](https://www.luogu.com.cn/problem/P4899)（建最小最大两个点 Kruskal 重构树后转化成二维数点） ------ ### 七、左偏树 左偏树是一种最常见且最好写的可并堆，在一些题目以及树形 DP 的优化方面有很好的表现。 ------ [P3377 【模板】左偏树](https://www.luogu.com.cn/problem/P3377)（左偏树模板题） [P4331 [BalticOI 2004] Sequence 数字序列](https://www.luogu.com.cn/problem/P4331)（堆维护中位数的套路，这里需要可并堆） [P3261 [JLOI2015] 城池攻占](https://www.luogu.com.cn/problem/P3261)（左偏树加速树形 DP 的例子，这题比 APIO 2012 那题相比多了标记，更具普遍性） ------ ### 八、线段树分治 线段树分治是一类非常重要的离线算法，修改的对象一般需要增删，而线段树分治可以通过离线转化为只有增而没有删，代价是多一个 log 的复杂度。 离线动态图就是它非常重要的应用。 ------ [P5787 二分图 /【模板】线段树分治](https://www.luogu.com.cn/problem/P5787)（线段树分治的最常见题目之一） [P3733 [HAOI2017] 八纵八横](https://www.luogu.com.cn/problem/P3733)（线段树分治和线性基的结合） [P3206 [HNOI2010] 城市建设](https://www.luogu.com.cn/problem/P3206)（线段树分治与 LCT 维护动态 MST 结合，可以支持增删的套路） 补充题：[LOJ 121 [离线可过] 动态图连通性](https://loj.ac/problem/121)（真正的线段树分治模板题，与可撤销并查集结合） 补充题：[LOJ 6515 [雅礼集训 2018 Day10] 贪玩蓝月](https://loj.ac/problem/6515)（线段树分治和背包 DP 结合的好题，化删为增） ------ ### 九、稍微涉及一些简单的字符串和图论技巧 如：后缀数组（SA），后缀自动机（SAM），最小生成树，Kruskal 重构树等。