企业官网建设流程全解析

“KY24 剩下的树”——看到这个题号，熟悉王道考研机试系列的朋友应该会心一笑。这道题几乎是所有“区间问题”的敲门砖：一条马路从0铺到L，每隔1米种一棵树，现在给你若干个拆迁区间，区间内的树全部拔掉，问最后还能剩下几棵。乍一看就是个小学数学加减法，但真正把它写对的人，比例远比你想象的低：端点算不算、区间重叠要不要去重、输入顺序乱不乱、数据范围大不大，每一步都藏着坑。这篇文章我把这道题的解法、推导、实战踩坑完整梳理一遍，给准备考研复试机试、算法竞赛入门，以及工作中经常要和区间数据打交道的朋友做个参考。

1. 先拆题：这道题到底在说什么

1.1 题面里的三个关键信息

原题描述很简短，但信息量其实不少。一条长度L的马路上，从坐标0开始，一直种到坐标L，注意是闭区间[0, L]，所以整条路上一共有L+1棵树，不是L棵。我第一次做这道题时就在这儿走神了，潜意识里总觉得“长度是L，树也是L棵”，结果答案差了1，排查了半天才发现是初始总数算错了。

接下来是M个区间。每个区间给两个整数，表示需要移除该范围内的所有树，包括两个端点。这里的“包括端点”是题目里最容易被忽略的限定，很多人栽跟头都是栽在这。比如区间[150, 300]，意味着坐标150上的树和坐标300上的树都要拔掉，它实际影响的是300 - 150 + 1 = 151棵树，而不是150棵。

最后一个关键信息是“区间可能重叠，且输入顺序不保证”。题目不会好心地帮你把区间排好序，也不会告诉你哪些区间互相覆盖。你要自己处理“同一个位置的树被多个区间重复点名”的问题。很多人在草稿纸上画线段时思路很清晰，一到代码里就忘了去重，导致最后被删的树被重复计算，剩余数量反而偏大。

1.2 为什么说它是区间处理的第一课

考研机试选择这道题当开篇，不是因为它难，而是因为它能精确地区分一个人到底懂不懂“区间操作”的本质。代码量很小，写完不超过五十行，但里面包含的考点一个都不少：闭区间的长度计算、重叠区间的合并、边界的处理、复杂度的权衡。

从知识体系上看，这道题至少能引出三套完全不同的解法：暴力标记、差分数组、区间合并。这三种思路分别对应了“模拟思维”“端点思维”和“数学思维”，后面你在做更复杂的区间问题——比如线段树覆盖、扫描线求面积、时间区间排重——时，都会反复用到同一套底层逻辑。所以我觉得，把这道题吃透，比刷十道重复的模拟题更有价值。

2. 从暴力到优雅：三种解法的演进

2.1 暴力标记：思路最直，但天花板低

暴力解法没什么技巧，开一个bool数组，长度为L+1，初始全部为true，表示每棵树的存活状态。每读到一个区间[l, r]，就从l循环到r，把对应的数组元素改成false。最后遍历一遍数组，统计true的个数。

这段代码大概十行，跑起来也很快，尤其是当L只有10000、M只有100的时候，最坏情况也就一百万次操作，任何语言都是一瞬间的事。所以很多人刷这道题时暴力一遍就过了，甚至不会再看其他解法。

但问题在于，这种解法的复杂度是O(L + M × avg_len)，取决于区间长度之和。一旦数据范围变成L = 10^9、M = 10^5，暴力就直接爆炸。更重要的是，暴力解法没有教给你任何“区间处理”的方法论，你只是机械地一遍遍去数组里打标记。后面遇到“区间修改、区间查询”的题目，你会发现这一套完全搬不过去。

我的建议是：暴力解法可以写，但只作为验证答案正确性的对照程序，别把它当最终方案。真正的洞见，要从后面两种思路里找。

2.2 差分数组：把区间操作变成端点操作

差分数组是一种特别“反直觉”但又特别优雅的思路。它不直接去标每棵树的状态，而是只记录“变化”发生在哪个位置。

我给你打个比方。假设你要统计一条街上每个小时内同时有多少个闹钟在响。最笨的办法是每个小时都把所有闹钟扫一遍；聪明的办法是只记录每个闹钟开始响的时刻和结束响的时刻：开始那一刻计数器+1，结束那一刻计数器-1，然后从头到尾扫一遍，边走边累加，就能知道任意时刻的响铃数量。

差分数组干的就是这件事。对于每个要移除的区间[l, r]，我们在diff[l]上加1，表示从坐标l开始，“被移除”的状态多了一层；在diff[r+1]上减1，表示从r+1开始，这层影响结束。全部区间记录完之后，从0到L扫一遍，用一个变量current做累加。current大于0的位置，说明至少被一个移除区间覆盖，树被拔掉了；current等于0的位置，说明没有任何区间覆盖到，树还在。

这里有三个细节必须解释清楚。

第一，为什么在r+1处减，而不是在r处减？因为区间是闭区间，r上的树也要被移除，所以“移除影响”必须持续到r+1才终止。如果你在r处减，那r这个点还没来得及被统计，current就已经归零了，r上的树会被误判为存活。

第二，diff数组要开L+2的长度。因为r+1最大会取到L+1，虽然我们扫描时只扫到L，但赋值时不能越界。开大一个位置，永远是区间题的第一安全法则。

第三，多个区间重叠时，current会累加成大于1的值。这没关系，我们只关心它是否等于0，不关心它具体是几。换句话说，被两个区间同时覆盖的树，也只会被判一次“已移除”，这正是我们要的效果。

差分数组的时间复杂度是O(L + M)，与区间长度无关，只与坐标范围和区间数量有关。它把原来“一个一个改”的问题，变成了“在端点处记录变化”的问题，这是区间类问题里非常核心的一次思维跃迁。

2.3 区间合并：排序后一次性算干净

如果说差分数组是“微观视角”，那区间合并就是“宏观视角”。它彻底不关心每一棵树的位置，而是把所有要移除的区间看成一条条线段，先把它们合并成若干个互不重叠的大区间，然后直接用数学公式计算总移除数量。

合并的流程是标准的三步：

第一步，把M个区间按左端点从小到大排序。如果左端点相同，就按右端点排序。排序的目的是保证我们扫描时，后面遇到的区间只会出现在当前合并区间的右边或上方，不会出现“回头”的情况。

第二步，维护当前合并区间的左右边界curL和curR。初始化为第一个区间的左右端点。然后逐个遍历后续区间，如果当前区间的左端点小于等于curR，说明它和当前合并区间有重叠，或者直接无缝衔接，那就把curR更新为max(curR, 当前区间的右端点)。否则，说明这个区间和前面的合并区间已经分开了，先把前面累计的移除长度结算掉，然后开启一个新的合并区间。

第三步，遍历结束后，把最后一个合并区间的长度也结算进去。

计算每个合并区间长度时，同样要注意闭区间：长度 = curR - curL + 1。最后剩下的树 = (L + 1) - 所有合并区间长度之和。

区间合并的最坏复杂度是O(M log M)，瓶颈在排序。和差分数组相比，它的优势是空间占用小，不依赖坐标范围，而且天然输出的是“合并后的区间”，后面如果要继续算“最长连续剩余段”之类的问题，这个结构直接就能用。

3. 手把手实现：从输入到输出

3.1 读入与边界处理

写代码之前，先把输入格式确认清楚。经典题目是多组输入还是单组输入，不同版本有细微区别，但稳妥的做法是写成“读到文件尾”的形式，这样单组、多组都能兼容。

while (scanf("%d%d", &L, &M) != EOF) { // 处理一组数据 }

如果题目明确说“M=0时结束”，那就在循环里加一个判断：

if (L == 0 && M == 0) break;

注意，这里判断的是L和M同时为0才退出。因为L=0但M不为0是合法的——马路长度为零，只有坐标0上一棵树，照样可以有区间来拔掉它。这个边缘情况我在测试时踩过，少写一个条件就会导致死循环或漏读。

另外，输入数据里可能有不讲武德的区间，让你遇到l > r的情况。虽然题目一般不会这么出，但写个swap保平安是很好的职业习惯。尤其在考研机试这种环境里，你不会想因为这种小问题浪费宝贵的调试时间。

3.2 差分数组版完整代码

下面是我推荐的解法，优先用差分数组，因为它代码短、复杂度稳定、不容易写错。

#include <cstdio> #include <cstring> #include <algorithm> const int MAXL = 10005; int diff[MAXL]; int main() { int L, M; while (scanf("%d%d", &L, &M) != EOF) { if (L == 0 && M == 0) break; memset(diff, 0, sizeof(diff)); for (int i = 0; i < M; i++) { int l, r; scanf("%d%d", &l, &r); if (l > r) std::swap(l, r); diff[l] += 1; diff[r + 1] -= 1; } int cur = 0; int ans = 0; for (int i = 0; i <= L; i++) { cur += diff[i]; if (cur == 0) ans++; } printf("%d\n", ans); } return 0; }

这段代码的核心就两个动作：读区间时改端点，扫描时累加判断。有人可能会问，为什么diff用int而不是bool？因为多个区间重叠时，diff[l]会累加多次，bool只能表示“有没有”，没法表示“叠加了几层”。虽然本题用bool也能凑合过，但只有int才能让你看清差分数组的本质。

用样例验证一下。输入：

500 3 150 300 100 200 470 471

坐标0到500共501棵树。差分操作后，扫描时current大于0的位置覆盖了[100, 300]和[470, 471]两个范围，总移除树数为(300-100+1) + (471-470+1) = 201 + 2 = 203棵。剩余501 - 203 = 298棵。程序输出298，和手算一致。

3.3 Python版实现与细节差异

如果用Python提交，思路完全一样，但有几个语法层面的点要小心。

import sys for line in sys.stdin: if not line.strip(): continue L, M = map(int, line.split()) if L == 0 and M == 0: break diff = [0] * (L + 2) for _ in range(M): l, r = map(int, sys.stdin.readline().split()) if l > r: l, r = r, l diff[l] += 1 diff[r + 1] -= 1 cur = 0 ans = 0 for i in range(L + 1): cur += diff[i] if cur == 0: ans += 1 print(ans)

第一，Python的sys.stdin迭代可能读到空行，所以加上了if not line.strip()的跳过逻辑，防止map函数解析报错。

第二，diff初始化用[0] * (L + 2)，这里的L+2和C++版里的MAXL同理，都是为了防止r+1越界。

第三，如果L特别大，比如到10^7以上，Python的纯循环扫描可能会比较慢。这种情况下，更推荐用区间合并写法，因为它的扫描次数取决于M而不是L。我把区间合并版也写出来了，和差分版形成互补。

#include <cstdio> #include <vector> #include <algorithm> int main() { int L, M; while (scanf("%d%d", &L, &M) != EOF) { if (L == 0 && M == 0) break; std::vector<std::pair<int, int>> segs; for (int i = 0; i < M; i++) { int l, r; scanf("%d%d", &l, &r); if (l > r) std::swap(l, r); segs.push_back({l, r}); } if (M == 0) { printf("%d\n", L + 1); continue; } sort(segs.begin(), segs.end()); int curL = segs[0].first; int curR = segs[0].second; long long removed = 0; for (int i = 1; i < M; i++) { if (segs[i].first <= curR) { curR = std::max(curR, segs[i].second); } else { removed += curR - curL + 1; curL = segs[i].first; curR = segs[i].second; } } removed += curR - curL + 1; printf("%lld\n", (long long)L + 1 - removed); } return 0; }

注意我在这里用了long long，因为虽然原题L只有10000，但万一出现10^9级别的扩展数据，int会溢出。在机试里，能用long long的地方就不要省，这不是秀技巧的地方。

4. 我踩过的坑和排查思路

4.1 坑一：端点到底删不删

这是最经典的低级错误。区间[l, r]的移除数量是r - l + 1，不是r - l。为什么会有人写错？因为很多人脑子里想的是“从第l棵到第r棵之间有几棵”，下意识觉得是“间隔数”，忘了我们要数的是端点本身。

这个错误在样例上很容易暴露。区间[470, 471]的移除数应该是2，如果写成471 - 470 = 1，最终答案就会变成299而不是298。你可以用这个样例来自检，输出298才是对的。

我自己的经验是，写代码前先在草稿纸上画一条数轴，把0和L标出来，再把样例区间标上去。画完再写代码，端点问题基本不会错。动笔之前花三十秒画图，能省掉半个小时的调试时间。

4.2 坑二：区间合并时该用<=还是<

区间合并的判断条件，我用的是segs[i].first <= curR，而不是<。为什么？这要回到树的坐标模型上来。

在“剩下的树”这道题里，树是种在整数坐标点上的，区间是闭区间。假设一个合并区间是[1, 2]，删掉的是坐标1和2上的树；下一个区间是[3, 4]，删掉的是坐标3和4上的树。坐标2和3之间还有没有树？没有了。所以这两个区间虽然中间没有重叠，但它们覆盖的树集合恰好是连续的，合并后等价于[1, 4]，不会多删任何一棵。

但如果换一个场景，区间表示的是连续实数范围，比如油漆一段墙面，[1, 2]和[3, 4]中间就有(2, 3)这一段没被覆盖，这时候就必须用<，不能合并。我遇到过不少把这两种模型搞混的人，在离散坐标题里用了<，导致删除对象被多算；在连续区间题里用了<=，导致覆盖范围被扩大。

所以这个细节不是死记硬背，而是要理解“区间里的对象是离散点还是连续值”。原题是离散树，用<=是安全的。

4.3 坑三：输入顺序、换行和EOF

机试环境里的输入读取是个隐形杀手。我见过有人写只处理一组数据的代码，样例能过，但提交后一直报错，就是因为题目有多组测试用例，程序只读了第一组就退出。

用while循环处理到EOF是标准做法。但这里还有一个更隐蔽的坑：如果使用Python，sys.stdin.readline()可能因为换行符或空行问题读出错误结构，建议每读一行都做strip处理。

另一个常见问题是，在读M个区间时，如果M=0，程序可能会访问空vector的第一个元素。我在区间合并版代码里特意加了一个M==0的判断，直接输出L+1。这种边缘情况在样例里通常没有，但不代表系统测试数据里没有。

4.4 一份自查清单

我把这道题容易翻车的点整理成了一张表，每次写完代码按这个列表过一遍，基本能保证一遍过。

这张表是我做区间类题目时的通用检查模板，不只是这一道题适用。凡是涉及“区间覆盖”“区间合并”的题目，我都会把这几项先过一遍。

5. 题目之外的延伸：这套思想能用到哪

5.1 线段树与扫描线的关系

把“剩下的树”这道题做完之后，很多人的困惑是：差分数组能解决一切吗？当然不能。差分数组适合“一次性把所有区间读进来，最后统一查询”的静态场景。但如果区间是动态的：一边修改（新增一个移除区间或恢复一段树），一边查询某段范围内剩余多少棵树，差分数组就无能为力了。

这时候就要上线段树。线段树的懒标记和区间更新，本质上做的就是“区间操作”的增量记录，和差分数组的核心思想一脉相承：不逐个元素处理，而是在区间层面记录变化。而扫描线算法更是把“端点事件”这一招发扬到了极致：矩形的左边界入队时+1，右边界出队时-1，然后扫描坐标轴，和差分数组处理闹钟的例子几乎一模一样。

所以说，这道题不是孤立的小题，它是整条算法知识链的起点。你会在这里第一次理解“端点记录变化”这件事，后面学线段树、树状数组、扫描线时，都会反复看到它的影子。

5.2 现实场景：时间区间、门店排期、日志去重

这套思想在工程上的应用也很广。最常见的例子是“给定一批会议时间区间，统计整个工作日里有多少分钟至少有人在开会”。把每个会议看成移除区间，把时间轴看成马路，把“被会议占用”看成“树被移除”，问题就一模一样。差分数组可以O(分钟数 + 会议数)地算出每个时间点同时开会的数量，比给每分钟打标记要快得多。

另一个例子是门店排期。很多连锁品牌会同时下发若干条促销活动时间，活动区间可能重叠，门店想知道“哪些日期完全没被任何活动覆盖”。这可以直接套区间合并的代码，把所有活动区间合并成互不重叠的时间段，剩下的空隙就是不活动的日期。你甚至可以顺手把合并后的区间输出，直接用来做备货计划。

日志去重也是类似场景。比如要统计一批故障记录实际覆盖的时间范围，记录之间可能重叠、可能无序，合并区间后得到的就是真实影响的连续时间窗口。处理这类问题，我几乎每次都直接从“剩下的树”的模板改过来，改改变量名就能用。

5.3 变种题：求最长连续剩余段

如果说“剩下的树”是区间合并的入门，那有一个变种题特别适合用来检验自己是否真的掌握了：不问你剩余多少棵树，而是问“剩余的树中，最长的连续一段有多少棵”。

这个变种用暴力也能做，但最优解可以直接站在区间合并的肩膀上。你先把所有移除区间合并，然后计算两个相邻合并区间之间的空隙长度，取最大值。注意最左端和最右端也要算：左边第一段从0到第一个合并区间的左端点之前，右边最后一段从最后一个合并区间的右端点之后到L。

整个逻辑就是在合并区间的基础上多了一次相邻元素的差值计算，代码量增加不超过十行。如果你能不看任何提示独立写出来，说明你对区间合并的理解已经到位了。我一般建议刷题时用一个变种题来检验自己是不是真的理解了原题，而不是背代码。

写在最后的一点个人习惯

这道题我自己刷了三遍。第一遍暴力模拟，跑过了样例就觉得完事了；第二遍学差分数组，才意识到原来不用一棵一棵标树；第三遍认真手写区间合并，才真正搞清楚那几种边界情况为什么这么处理。说实话，一遍遍重写不是因为我记性差，而是每次写都会对“区间”这个概念多一层体感。

最后分享一个我自己的小习惯：遇到任何区间类题目，先问自己三个问题——需不需要保留每一棵树的精确状态？区间数量大还是坐标范围大？查询是静态还是动态？这三个问题的答案基本能直接指向暴力、差分、区间合并、线段树中的某一个方案。这套判断流程帮我省过很多弯路，也希望你能在刷题过程中慢慢建立起自己的套路。