ACM Template of kuangbin
3 数据结构 56
3.1 划分树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2 RMQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2.1 一维 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2.2 二维 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.3 树链剖分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.3.1 点权 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.3.2 边权 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.4 伸展树（splay tree） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.4.1 例题：HDU1890 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.4.2 例题：HDU3726 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.5 动态树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.5.1 SPOJQTREE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.5.2 SPOJQTREE2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.5.3 SPOJQTREE4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.5.4 SPOJQTREE5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.5.5 SPOJQTREE6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.5.6 SPOJQTREE7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.5.7 HDU4010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.6 主席树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.6.1 查询区间多少个不同的数 . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.6.2 静态区间第 k 大 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.6.3 树上路径点权第 k 大 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.6.4 动态第 k 大 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
3.7 Treap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.8 KD 树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.8.1 HDU4347 K 近邻 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.8.2 CF44G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
3.8.3 HDU4742 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
3.9 替罪羊树 (ScapeGoat Tree) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.9.1 CF455D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.10 动态 KD 树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
3.11 树套树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.11.1 替罪羊树套 splay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4 图论 130
4.1 最短路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.1.1 Dijkstra 单源最短路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.1.2 Dijkstra 算法 + 堆优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.1.3 单源最短路 bellman_ford 算法 . . . . . . . . . . . . . . . . . . . . . . . 131
4.1.4 单源最短路 SPFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.2 最小生成树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.2.1 Prim 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.2.2 Kruskal 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.3 次小生成树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
4.4 有向图的强连通分量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
4.4.1 Tarjan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
4.4.2 Kosaraju . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
4.5 图的割点、桥和双连通分支的基本概念 . . . . . . . . . . . . . . . . . . . . . . . 138
4.6 割点与桥 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
4.6.1 模板 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
kuangbin 2
