《算法竞赛进阶指南》0x40数据结构进阶
题单介绍
# 《算法竞赛进阶指南》0x40数据结构进阶
upd on 2022.7.4 更新部分排版（~~其实早在一年多前就有了这个念头~~）
upd on 2023.3.8 删除了双倍经验
感谢 [eastcloud](https://www.luogu.com.cn/user/421265) 和 [Fish_Clever](https://www.luogu.com.cn/user/104918) 对本题单提出的建议。
## 例题
### 0x41 并查集
- 程序自动分析【NOI2015/BZOJ4195】[P1955](https://www.luogu.com.cn/problem/P1955)
- Supermarket【POJ1456】[UVA1316](https://www.luogu.com.cn/problem/UVA1316)
- 银河英雄传说【NOI2002/CH4101】[P1196](https://www.luogu.com.cn/problem/P1196)
- Parity game【POJ1733】[P5937](https://www.luogu.com.cn/problem/P5937)
- 食物链【NOI2001/POJ1182】[P2024](https://www.luogu.com.cn/problem/P2024)
### 0x42 树状数组
- 楼兰图腾【CH4201】
[AcWing241](https://www.acwing.com/problem/content/243/)
- A Tiny Problem with Integers【】[P3368](https://www.luogu.com.cn/problem/P3368)
- A Simple Problem with Integers【POJ3468】[P3372](https://www.luogu.com.cn/problem/P3372)
- Lost Cows【POJ2182】[AcWing244](https://www.acwing.com/problem/content/245/)
### 0x43 线段树
- Can you answer these queries III【CH4301】[SP1716](https://www.luogu.com.cn/problem/SP1716)
- Interval GCD【CH4302】
[AcWing246](https://www.acwing.com/problem/content/247/)
- A Simple Problem with Integers【POJ3468】[P3372](https://www.luogu.com.cn/problem/P3372)
- Atlantis【POJ1151】[P5490](https://www.luogu.com.cn/problem/P5490)
- Stars in Your Window【POJ2482】[P1502](https://www.luogu.com.cn/problem/P1502)
### 0x44 分块
- A Simple Problem with Integers【POJ3468】[P3372](https://www.luogu.com.cn/problem/P3372)
- 蒲公英【BZOJ2724/CH4401】[P4168](https://www.luogu.com.cn/problem/P4168)
- 磁力块【CH#46A】
[AcWing250](https://www.acwing.com/problem/content/252/)
- 小Z的袜子【BZOJ2038】[P1494](https://www.luogu.com.cn/problem/P1494)
### 0x45 点分治
- Tree【POJ1741】
[AcWing252](https://www.acwing.com/problem/content/254/)
### 0x46 二叉查找树与平衡树初步
- 普通平衡树【BZOJ3224/CH4601】[P3369](https://www.luogu.com.cn/problem/P3369)
### 0x47 离线分治算法
- 天使玩偶【BZOJ2716/CH4701】[P4169](https://www.luogu.com.cn/problem/P4169)
- K-th Number【POJ2104】[SP3946](https://www.luogu.com.cn/problem/SP3946)
### 0x48 可持久化数据结构
- 最大异或和【BZOJ3261】[P4735](https://www.luogu.com.cn/problem/P4735)
- K-th Number【POJ2104】[SP3946](https://www.luogu.com.cn/problem/SP3946)
## 练习（0x49 总结与练习）
1. 完成本章中所有例题的代码实现
2. 关押罪犯【NOIP2010/CH4901】[P1525](https://www.luogu.com.cn/problem/P1525)
3. Rochambeau【POJ2912】
[AcWing258](https://www.acwing.com/problem/content/260/)
4. True Liars【POJ1417】
[AcWing259](https://www.acwing.com/problem/content/261/)
5. Buy Tickets【POJ2828】
[AcWing260](https://www.acwing.com/problem/content/262/)
6. Hotel【POJ3667】[P2894](https://www.luogu.com.cn/problem/P2894)
7. Picture【IOI1998/POJ1177】[P1856](https://www.luogu.com.cn/problem/P1856)
8. 作诗【BZOJ2821/CH4907】[P4135](https://www.luogu.com.cn/problem/P4135)
9. Race【IOI2011/BZOJ2599/CH4908】[P4149](https://www.luogu.com.cn/problem/P4149)
10. 营业额统计【BZOJ1588】[P2234](https://www.luogu.com.cn/problem/P2234)
11. SuperMemo【POJ3580】
[AcWing266](https://www.acwing.com/problem/content/268/)
12. Mokia【BZOJ1176】[P4390](https://www.luogu.com.cn/problem/P4390)
13. Meteors【BZOJ2527/CH4912】[P3527](https://www.luogu.com.cn/problem/P3527)
14. Fotile 模拟赛 L【BZOJ2741】
[AcWing269](https://www.acwing.com/problem/content/271/)
15. 可持久化并查集加强版【BZOJ3674】[P3402](https://www.luogu.com.cn/problem/P3402)（无强制在线）；[AcWing270](https://www.acwing.com/problem/content/272/)（强制在线）
### 练习的提示：
2. 并查集/扩展域或边带权，贪心
3. 并查集/扩展域或边带权
4. 并查集+背包
5. 树状数组
6. 线段树
7. 扫描线
8. 分块
9. 点分治
10. 平衡树
11. 平衡树
12. CDQ分治，容斥原理
13. 整体分治
14. 分块+可持久化Trie
15. 可持久化线段树+并查集按秩合并