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