BF的数据结构题单-提高组

# Part 1 此部分难度应该不会超过提高组。 [省选树形数据结构题单 1](https://www.luogu.com.cn/training/1176) [省选树形数据结构题单 2](https://www.luogu.com.cn/training/4897) [省选根号数据结构题单](https://www.luogu.com.cn/training/3238) 未来的省选题单会不断更新，也请大家关注。 如果在我做题的过程中看到一些有趣的题也会加入的。 update：增加一些杂项数据结构（见最后） ## 并查集 这一数据结构很基础，但同样容易被忽视。 ### 连通性判断 - [P1197 [JSOI2008]星球大战](https://www.luogu.com.cn/problem/P1197) - [P1783 海滩防御](https://www.luogu.com.cn/problem/P1783) ### 非加权维护 - [P1525 关押罪犯](https://www.luogu.com.cn/problem/P1525) - [P2024 [NOI2001]食物链](https://www.luogu.com.cn/problem/P2024) ### 加权维护 - [P1196 [NOI2002]银河英雄传说](https://www.luogu.com.cn/problem/P1196) - [P5092 [USACO04OPEN]Cube Stacking](https://www.luogu.com.cn/problem/P5092) ## 树状数组/线段树 这两种数据结构很相似，故在此作为同一种数据结构处理。 由于此数据结构题目较多，故我会尽量精简。 ### 维护复杂信息 - [P2574 XOR的艺术](https://www.luogu.com.cn/problem/P2574) - [P2894 [USACO08FEB]酒店Hotel](https://www.luogu.com.cn/problem/P2894) - [P4145 上帝造题的七分钟2 / 花神游历各国](https://www.luogu.com.cn/problem/P4145) - [P4513 小白逛公园](https://www.luogu.com.cn/problem/P4513) - [P2572 [SCOI2010]序列操作](https://www.luogu.com.cn/problem/P2572) - [P5889 跳树](https://www.luogu.com.cn/problem/P5889) - [P6186 [NOI Online 提高组]冒泡排序](https://www.luogu.com.cn/problem/P6186) ### 权值树基础 关于平衡树，它。。。 但权值树真的有很多的作用呢！ - [P3369 【模板】普通平衡树](https://www.luogu.com.cn/problem/P3369) - [P1972 [SDOI2009]HH的项链](https://www.luogu.com.cn/problem/P1972) - [P4113 [HEOI2012]采花](https://www.luogu.com.cn/problem/P4113) ### 扫描线问题 - [P5490 【模板】扫描线](https://www.luogu.com.cn/problem/P5490) - [P1856 [USACO5.5]矩形周长Picture](https://www.luogu.com.cn/problem/P1856) - [P1904 天际线](https://www.luogu.com.cn/problem/P1904) ### 二维偏序 - [P1502 窗口的星星](https://www.luogu.com.cn/problem/P1502) - [P5816 [CQOI2010]内部白点](https://www.luogu.com.cn/problem/P5816) - [P3431 [POI2005]AUT-The Bus](https://www.luogu.com.cn/problem/P3431) ### 树链剖分 一些基础的树上问题，对 noip 也许会有帮助。 - [P3384 【模板】重链剖分](https://www.luogu.com.cn/problem/P3384) - [P2590 [ZJOI2008]树的统计](https://www.luogu.com.cn/problem/P2590) - [P3178 [HAOI2015]树上操作](https://www.luogu.com.cn/problem/P3178) - [P2680 运输计划](https://www.luogu.com.cn/problem/P2680) ## 杂题 其实还有提高还有一些比较简单的数据结构，比如 st 表，单调栈等等。在此给出一些题目，可能会用到多种数据结构，难度较为简单。 - [P3865 【模板】ST表](https://www.luogu.com.cn/problem/P3865) - [P5629 【AFOI-19】区间与除法](https://www.luogu.com.cn/problem/P5629) - [P1886 滑动窗口 /【模板】单调队列](https://www.luogu.com.cn/problem/P1886) - [P2216 [HAOI2007]理想的正方形](https://www.luogu.com.cn/problem/P2216) - [P2564 [SCOI2009]生日礼物](https://www.luogu.com.cn/problem/P2564) - [P5788 【模板】单调栈](https://www.luogu.com.cn/problem/P5788) - [P1169 [ZJOI2007]棋盘制作](https://www.luogu.com.cn/problem/P1169) - [P4147 玉蟾宫](https://www.luogu.com.cn/problem/P4147)