吴铭世的推平树专题（珂朵莉树）
题单介绍
本题单由B站逗比的吴铭世整理，详细推平树（珂朵莉树）教程欢迎点击 ~~这里~~ 查看。
哦对，教程还在施工中，做好了后链接会贴上来（预计6月份完成视频，会考虑再做一个图文版投稿洛谷日报）。
需要强调的一点是，本题单不保证按照**推平树（珂朵莉树）做法难度**升序排序，而是按照洛谷提供的难度标签进行排名。
此外，额外推荐吴铭世自制的**模板题目系列题单**，链接在 [ 这里 ](https://www.luogu.com.cn/training/318385)，题目将不断更新，如果有任何建议欢迎通过洛谷或B站直接私信！
另外，所有题目仅保证可以使用50%以上的推平树（珂朵莉树）获得部分分数，不保证能够完全AC，不能AC的我会在下方列出。（话说啥时候能有题只能用推平树做，能卡掉其他的数据结构啊！？)
接下来，我将对具体每一道题目进行详细评析，内容涉嫌大量透题，建议做完题目之后再看。
| 题目编号 | 题目名称 | 题目难度 | 题目考点 |
|:-:|:-:|:-:|:-:|
| P1047 | 校门外的树 | 入门 | 推平策略与结点计数 |
| P1276 | 校门外的树（增强版） | 普及- | 推平策略与结点计数 |
| P1204 | 挤牛奶 | 普及- | 推平策略与结点计数 |
| SP13035 | 数质数 | 普及/提高- | 推平+质数筛 |
| P2082 | 区间覆盖(plus) | 普及/提高- | 推平策略与结点计数 |
| P1840 | 轴着色 | 普及/提高- | 推平策略与结点计数 |
| P3740 | 贴海报 | 普及+/提高 | 推平策略与结点计数 |
| P1253 | 扶苏的问题 | 普及+/提高 | 推平等经典区间操作，但由于存在两个测试点不存在推平操作，推平树只能跑80pts |
| CF915E | 物理课 | 提高+/省选- | 推平策略与结点计数 |
| P5568 | 校门外的区间 | 提高+/省选- | 推平与集合维护 |
| P2787 | 理理思维 | 提高+/省选- | 推平与若干暴力操作，但最后一个测试点在推平收敛前询问次数过多会TLE，推平树满分90pts |
| P4979 | 矿洞：坍塌 | 提高+/省选- | 推平与沟巴询问，但若干测试点在推平收敛前询问次数过多会TLE，推平树被卡了 |
| P2894 | G宾馆 | 提高+/省选- | 推平策略与结点计数 |
| P1382 | 楼房 | 提高+/省选- | 二维推平树，注意卡常即可 |
| CF558E | 简单任务 | 提高+/省选- | 考虑大量字母相同且连续变相推平+排序 |
| P5358 | 快速查询 | 提高+/省选- | 读入有点恶心，但是是裸的推平树 |
| CF620E | 新年树 | 提高+/省选- | 树链剖分+推平树，能过到#66，后面的测试点推平树被卡掉了QAQ |
| CF343D | 水树 | 提高+/省选- | 树剖加推平树，代码上恶心一点，但可以AC过掉！ |
| P2391 | 白雪皑皑 | 提高+/省选- | 推平策略与结点计数，数据挺水的 |
| CF444C | DZY爱颜色 | 提高+/省选- | 线段树套推平树即可 |
| CF868C | 珂朵莉 | 省选/NOI- | 推平树起源题，裸的推平树暴力AC |
| CF817F | MEX | 省选/NOI- | 裸的推平树区间操作，可以直接AC |
| P5350 | 序列 | 省选/NOI- | 裸的推平树，可以暴力AC，但是细节较多，容易出现莫名MLE/RE的问题，需要耐心考虑各种细节！|
| SP19568 | 质数询问 | 省选/NOI- | 推平树+欧拉筛直接AC |
| P4130 | 项链工厂 | 省选/NOI- | 环形推平树，比较有意思，但是目前推平树做法被卡了QAQ |
| P7735 | 轻重边 |省选/NOI- | 树链剖分+推平树，需要卡常 |
| P5500 | 不女装 | 省选/NOI- | 裸的推平树，但是对于80%的数据保证能卡飞推平树，只能拿20pts |
| CF803G | 循环RMQ | 省选/NOI- | 裸的推平树，可以直接AC（目前） |
| SP6779 | 你行吗？| 省选/NOI- | 树链剖分+推平树，需要卡常 |
| CF1136E | 不写传奇 | 省选/NOI- | 循环推平，裸的推平树 |
| P4344 | 脑洞治疗仪 | 省选/NOI- | 推平树被卡了直接吃糖QAQ |
| P2572 | 序列操作 | 省选/NOI- | 定期重构链表式推平树可以过，但传统推平树会被卡 |
| CF1638E | 颜色の操作 | 省选/NOI- | 推平树+树状数组可以直接AC |
| P8512 | 152测试 | 省选/NOI- | 推平树+回滚莫队+卡常=AC，当然也可以推平树+树状数组，但思维难度相对较高，可以直接AC掉 |
| P5251 | 第二代图灵机 | NOI/NOI+/CTSC | 推平树+线段树+双指针+卡常=AC |
| P7582 | 风雨 | NOI/NOI+/CTSC | 将问题转化求为区间内字符串在母串出现次数，可使用推平树+线段树进行维护，可以获得60pts（4个测试点没有推平操作）。特判不推平操作情况使用AC自动机，本题目可以直接100pts（AC） |
| P7983 | 练习Z |NOI/NOI+/CTSC | 裸的推平树只能过Subtask4从而获得20pts的高分。本题可采用推平树的思路分块维护，想AC确实非常有难度。 |
| P4690 | 镜中的昆虫 | NOI/NOI+/CTSC | 裸的推平树，但是被卡了，只能拿10pts，但是评论区里有我的弱化版 |