1. 从一道“送分题”开始：P1047 到底在考什么
第一次在洛谷题库里翻到 P1047 校门外的树，是在我刚开始系统性刷 NOIP 普及组真题的时候。说实话，这道题对新手相当友好，但如果你只是照着 AC 代码抄一遍、跑通样例就往下走，那大概率会漏掉一些对后续刷题很有用的东西。我见过不少人刚刷完这道题就直接冲 P1843 那种带权覆盖问题，结果思路完全拧不过来，就是因为基础题的细节没吃透。
P1047 的题干并不复杂：一条长度为 L 的马路，从坐标 0 到 L 一共 L+1 棵树，移走若干个给定区间内的树（区间端点上的树也算移走），求最后剩下的树的数量。输入第一行是两个整数 L 和 M，后面跟 M 行，每行两个整数表示一个闭区间 [u, v]。输出是剩余的树数。数据范围不算大，所以解法非常多，但不同解法背后的思想差异，才是这道题真正的价值所在。
这道题适合的人群大致是三类：刚接触算法竞赛、正在做入门循环与数组练习的初中生；准备 NOIP 普及组、CSP-J 复赛、需要巩固模拟与差分思想的选手；还有像我一样想拿经典题做模板、总结套路的老手。无论你属于哪一类，把 P1047 的几种解法都吃透，比急着刷十道类似的题更有用。
2. 核心思路拆解：为什么要先想“选什么算法”而不是“能不能过”
2.1 数据范围决定了你的第一版代码
很多新手拿到题的第一反应是“直接模拟”，也就是开一个足够大的布尔数组，把马路上的每一棵树标记为“存在”，然后对每个区间做一次遍历，把区间内的树标记为“移除”。最后统计一下还剩多少个 true 就行。
这种做法在 P1047 原版的数据范围下没有任何问题，因为 L 和 M 都很小，哪怕你用最笨的双层循环，总操作量也不过是 L 乘以 M 的级别，轻松跑过。但问题在于，很多人写代码时根本不去算这个操作量到底是多少，只是“感觉能过”，或者“样例过了就交”。这就是我会反复强调的一点：拿到任何题目，第一步不是写代码，而是根据数据范围估算时间复杂度，然后选一个设计上就合理的算法。
P1047 原版的 L 最大只有 10000，M 最大只有 100，所以暴力的总操作量是 10^6 级别，完全没压力。但如果数据范围变成 L=10^9、M=10^5，这个“直接开数组模拟”的想法就立刻作废了。所以从学习角度，我建议你至少准备两种解法，而不是只背一种。
2.2 模拟标记法和差分解法的本质差异
模拟标记法的核心思想是“把树直接映射成数组下标”。思路非常直觉：既然每棵树有一个整数坐标，那我就用一个数组标记它是否被移走。这种做法的优点是容易理解、不易写错，缺点是当坐标范围太大时无法开数组。
差分解法的核心思想则是“不标记每一棵树，而是记录区间边界的变化量”。具体来说，开一个差分数组 d，对于每个区间 [u, v]，执行 d[u]++ 和 d[v+1]--，表示从 u 位置开始多覆盖了一层，从 v+1 位置开始少覆盖了一层。处理完所有区间之后做一次前缀和，就能得到每个坐标被覆盖的次数，次数大于 0 就说明该位置的树被移走了。
这两种思路本质上是从“点视角”切换到“区间视角”。我经常用一个生活化的类比：标记数组就像你一张一张地翻日历，把每个被占用的日期划掉；差分数组则像你在日历上只记录“从哪天开始忙”和“从哪天开始闲”，最后顺着日期一天天累加，就知道哪天是空的、哪天有安排。
2.3 为什么差分能成为进阶的跳板
理解了差分，你其实已经掌握了一种非常通用的区间处理工具。比如那道热词里的“洛谷 1843”，虽然题目场景完全不同，但如果你能把区间覆盖的操作拆成差分，再配合二分答案，思路就会清晰很多。再比如遇到需要多次区间修改、单点查询的问题，差分几乎是最快的入门方案。
所以我的建议是：P1047 你可以用暴力过题，但一定要再手写一遍差分版本。不是为了炫技，而是为了在低成本的题目里提前熟悉一个高频考点。等你哪天刷到区间合并、扫描线、树状数组修区间，你会发现差分的身影无处不在。
3. 实操过程与代码实现：从暴力到差分，一步一个脚印
3.1 暴力模拟版本（适合入门理解题意）
先看最直接的写法。我用 C++ 实现，因为 NOIP 系列比赛主流环境就是 C++，洛谷的评测机也完全支持。
#include <bits/stdc++.h> using namespace std; int main() { int L, M; cin >> L >> M; vector<bool> tree(L + 1, true); // 0 到 L，共 L+1 棵树 for (int i = 0; i < M; i++) { int u, v; cin >> u >> v; for (int j = u; j <= v; j++) { tree[j] = false; } } int cnt = 0; for (int i = 0; i <= L; i++) { if (tree[i]) cnt++; } cout << cnt << endl; return 0; }这个版本的核心点有两个。第一，数组大小是 L+1 而不是 L，因为坐标 0 到 L 一共包含 L+1 个整数位置，少了 1 棵树就是边界错误。第二，区间是闭区间，所以循环里 j<=v 而不是 j<v，别小看这个等号，我第一次写这题时就是这样 WA 了一次。
vector 在 C++ 里是一个特化版本，占用空间是按位压缩的，所以哪怕 L 稍微大一点，这个标记数组也很省。不过如果转用普通 vector 或 int 数组，写法上差别不大，用 bool 只是语义更清晰。
3.2 差分版本（推荐重点学习）
接下来是差分版本。代码很短，但你要确保自己真的理解每一行在做什么。
#include <bits/stdc++.h> using namespace std; int main() { int L, M; cin >> L >> M; vector<int> diff(L + 2, 0); // 注意开到 L+2，因为可能出现 v+1 = L+1 的情况 for (int i = 0; i < M; i++) { int u, v; cin >> u >> v; diff[u]++; diff[v + 1]--; } int cover = 0; int ans = 0; for (int i = 0; i <= L; i++) { cover += diff[i]; if (cover == 0) ans++; } cout << ans << endl; return 0; }为什么 diff 数组要开到 L+2？因为当 v 恰好等于 L 时，v+1 = L+1，这个位置虽然不表示任何树，但它是差分数组的“哨兵”，用来让前缀和正确地减掉覆盖次数。如果你数组只开到 L+1，访问 diff[L+1] 就会越界，洛谷的评测机会直接给你 RE。
理解 cover 这个变量的变化过程很重要。初始为 0，表示当前位置之前没有任何区间覆盖。遇到 diff[i] 的累加值改变，说明从 i 这个位置开始，有新的区间进入或者旧的区间结束。只有 cover == 0 的位置，才说明没有任何区间覆盖到它，树还在。
我在实际测试中发现一个非常值得注意的点：差分版本的循环边界条件，和暴力版本一样，都要从 0 走到 L，不要写成 1 到 L。这道题的坐标系统从 0 开始，是诱导新手出错的高频坑。
3.3 区间合并版本（以后刷区间题用得上）
除了暴力和差分，还有一种思路也值得提一下，就是先按左端点排序，然后合并所有重叠区间，最后统计这些被覆盖的区间长度总和，再用 (L+1) 减去它。
#include <bits/stdc++.h> using namespace std; int main() { int L, M; cin >> L >> M; vector<pair<int, int>> segs(M); for (int i = 0; i < M; i++) { cin >> segs[i].first >> segs[i].second; } sort(segs.begin(), segs.end()); int covered = 0; int curL = segs[0].first, curR = segs[0].second; for (int i = 1; i < M; i++) { if (segs[i].first <= curR) { curR = max(curR, segs[i].second); } else { covered += curR - curL + 1; curL = segs[i].first; curR = segs[i].second; } } covered += curR - curL + 1; cout << (L + 1) - covered << endl; return 0; }这个解法在 P1047 原版里属于“杀鸡用牛刀”，但它是一个非常重要的区间处理范式。以后你刷“合并区间”、“会议室预定”这类题目时，这个模板可以直接迁移。我甚至建议你把这段代码背下来，因为在一些省份的编程题里，区间合并的频率不低。
此时你可能会问，三种解法我到底该写哪一种上提交？我的建议是：比赛里看数据范围选，平时练习里全写一遍。原版数据写暴力或差分都能过，但如果你准备的是 CSP-J 复赛，差分一定要熟到闭着眼能打出来。
4. 常见问题与 Debug 实录：那些年我在 P1047 上踩过的坑
4.1 高频 Bug：区间端点理解错误
我见过最多的 WA 原因，是把“闭区间”理解成“左开右闭”或者“全开区间”。题目说的是“移走这棵树”，所以区间两端的树都要移走。如果你用的是 j<v 而不是 j<=v，样例可能还能过，因为样例数据恰好没有暴露这个错误，但一旦区间覆盖到了端点树，输出就会错。
我习惯的做法是，写完代码后先自己构造一个全边界用例测一下。比如 L=3，一个区间 [0,3]，正确答案应该是 0。如果代码输出 1，那就说明端点上少减了一棵树。这个自查习惯能帮你省下好几分钟的罚时。
4.2 数组越界：差分数组多开一个位置不是玄学
差分版本最容易越界的地方我已经提过，就是 diff[v+1] 中的 v+1 可能等于 L+1。由于前缀和只在 0 到 L 范围内计算，所以 diff[L+1] 本身是否被累加并不会影响答案，但如果数组没开够，程序运行到那里就会产生未定义行为。
我在本地测试时曾经用 L=10 的小数据跑，一切正常，一提交就 RE。后来查了半天才发现是数组越界。从那次起，我养成了一个习惯：只要代码里出现 i+1 或者 i-1 这类下标偏移，就先检查数组大小是不是留足了余量。尤其是差分这种在边界处做减法的写法，数组多开两个位置永远是保险的。
4.3 彻底清除“区间覆盖次数”的误区
还有一个理解层面的问题，新手很容易混淆“被覆盖过的位置”和“被覆盖了多次的位置”。如果用布尔标记，这个问题不显眼，因为 true 变成 false 之后重复移走也没有影响。但如果你用整数数组记录覆盖次数，最后统计时可能犯糊涂：到底是只数那些等于 0 的位置，还是数那些等于 1 的位置？
答案很明确：只要覆盖次数大于等于 1，树就已经被移走了。所以最终统计的是覆盖次数为 0 的位置数量。我曾经看到有人统计 cover==1 的位置，然后理所应当地认为“这些是只被移走一次的树”，完全没搞懂差分数组的语义。这点在理解前缀和时一定要想透。
注意：差分数组中某个位置累加后的值，代表的是“该坐标被多少个区间覆盖”，不是“该坐标上树的移除状态”。二者在“被覆盖过”这个含义上等价，但只有在 cover == 0 时树才存活。
4.4 常见问题速查表
| 症状 | 可能原因 | 解决方向 |
|---|---|---|
| 样例通过但提交 WA 部分点 | 区间端点处理错误（应该是闭区间却写成开区间） | 检查 j<=v 和差分里的 diff[v+1]-- |
| 提交后 RE | 数组越界，特别是 diff[v+1] 越界 | 数组大小至少开到 L+2 |
| 输出结果整体偏大 | 统计范围写错，比如从 1 数到 L，漏掉了坐标 0 | 循环范围改用 i=0; i<=L; i++ |
| 数据稍大就超时 | 使用了 O(n*m) 暴力，且数据规模远超原版 | 改用差分或区间合并，把复杂度降到 O(n+m) |
| 看不出哪里有错 | 样例太弱，边界没测 | 造边界数据自查，比如 L=0、区间覆盖到 0 或 L |
我之前刷洛谷小游戏板块的时候，还发现不少同学用“校门外的树”这道题来测试自己的可视化交互代码，比如在地图上模拟移除树木的动态过程。这其实是个很好的拓展思路，因为算法题的输入输出本身是无趣的，但一旦你把它移植成实际场景，理解感会完全不同。
5. 从 P1047 扩散开去：同类题型的延展与竞赛思维
5.1 变体一：区间可能重叠（区间合并的需求，对应 P1047 加强版）
原版 P1047 的区间是随意的，可能重叠也可能不重叠。但如果你用暴力标记，重叠不重叠根本不会影响答案，这也是为什么很多新手能轻松 AC 的原因。
但洛谷上有一道著名加强版，L 可以放大到 10^9，M 也大幅增加，暴力直接暴毙。此时你只有两条路：要么用差分（但最终你仍需要扫描整个 0 到 L 的范围，空间上会有新问题），要么用区间合并。区间合并的核心思想是：把重复的覆盖先合并成互不重叠的大区间，然后对每条区间计算长度累加。这里就体现了我前面让你背区间合并模板的价值。
5.2 变体二：求被覆盖的最长连续段（需要扫描或动态维护）
还有一类题目，让你找“最长连续没有被覆盖的区间”，或者“最长连续被覆盖的区间长度”。这类题就要在差分数组做完前缀和之后，用双指针法扫描一遍。P1047 虽然不直接问这个，但你只要把统计剩余树的逻辑稍作修改，就能实现。
我在热词里看到“洛谷 2569”和“洛谷 p7074”，这些题的题面虽然完全不是树和马路，但处理区间覆盖、连续段的方式，很多都能溯源到 P1047 这道基础题。学算法最忌讳的就是一题一题孤立着刷，多去做这种“从 A 题的方法到 B 题的迁移”，你的竞赛水平会提升得很快。
5.3 给准备 NOIP 普及组的选手的建议
如果你正在备战 NOIP 2005 年之后那些普及组试题，我的建议是：把 2005 年到 2010 年的每道普及组真题都当成“知识点索引”，而不是“任务清单”。比如 P1047 这道题背后的知识点是模拟、差分、区间处理；同时期的其他题目各有侧重，刷完一题就回头总结它的考点。
另外一个建议是，刷题时尽量做到“一题多解”。P1047 就是一个很好的演练场：暴力标记是模拟，差分是数据结构思想的启蒙，区间合并是贪心排序的典型。同一道题，三种写法，三种收获。如果条件允许，我甚至建议你把三种代码都提交一遍，看看它们在评分上的差异。
6. 我的实战心得：这样刷 P1047 收益最高
最后分享一点个人经验。我在最初刷洛谷时，特别喜欢跳过“简单题”，总觉得普及组第一题不值得花时间。后来被一道区间覆盖的题卡住，回头研究 P1047 的差分版本时才发现自己对差分的理解一直停留在“会写模板但不懂原理”的层次。从那以后我就改了习惯：凡是普及组真题里的简单题，我都要求自己至少想出两种解法并写出来提交。
这带来的好处非常明显。比如我在热词里看到“洛谷 1048”这道题，它同样是普及组经典，但考点是 0/1 背包，跟 P1047 完全不同。可我在做 P1047 差分时养成的“先分析数据范围再定算法”的习惯，做 1048 时依然帮我避开了几个坑。算法题之间表面上千差万别，但底层思维是互通的。
还有一个小技巧分享：在洛谷做题时，我习惯先看这道题在“题解区”里被点踩最多的那篇题解，因为那往往是思路有问题或者代码有坑的代表。P1047 的题解区里就有一篇经典的“差分解法误区”讨论，我当初就是从争论里彻底搞懂 diff[v+1]-- 为什么必须存在的。
如果你也是刚开始接触算法竞赛，那 P1047 是个非常理想的起点。它不会让新手挫败感拉满，也不会简单到毫无收获。认真手写一遍暴力、差分、区间合并三个版本，再逼自己把每一处边界条件讲清楚，你的入门基础就稳稳地打下来了。
