“KY24 剩下的树”——看到这个题号熟悉王道考研机试系列的朋友应该会心一笑。这道题几乎是所有“区间问题”的敲门砖一条马路从0铺到L每隔1米种一棵树现在给你若干个拆迁区间区间内的树全部拔掉问最后还能剩下几棵。乍一看就是个小学数学加减法但真正把它写对的人比例远比你想象的低端点算不算、区间重叠要不要去重、输入顺序乱不乱、数据范围大不大每一步都藏着坑。这篇文章我把这道题的解法、推导、实战踩坑完整梳理一遍给准备考研复试机试、算法竞赛入门以及工作中经常要和区间数据打交道的朋友做个参考。1. 先拆题这道题到底在说什么1.1 题面里的三个关键信息原题描述很简短但信息量其实不少。一条长度L的马路上从坐标0开始一直种到坐标L注意是闭区间[0, L]所以整条路上一共有L1棵树不是L棵。我第一次做这道题时就在这儿走神了潜意识里总觉得“长度是L树也是L棵”结果答案差了1排查了半天才发现是初始总数算错了。接下来是M个区间。每个区间给两个整数表示需要移除该范围内的所有树包括两个端点。这里的“包括端点”是题目里最容易被忽略的限定很多人栽跟头都是栽在这。比如区间[150, 300]意味着坐标150上的树和坐标300上的树都要拔掉它实际影响的是300 - 150 1 151棵树而不是150棵。最后一个关键信息是“区间可能重叠且输入顺序不保证”。题目不会好心地帮你把区间排好序也不会告诉你哪些区间互相覆盖。你要自己处理“同一个位置的树被多个区间重复点名”的问题。很多人在草稿纸上画线段时思路很清晰一到代码里就忘了去重导致最后被删的树被重复计算剩余数量反而偏大。1.2 为什么说它是区间处理的第一课考研机试选择这道题当开篇不是因为它难而是因为它能精确地区分一个人到底懂不懂“区间操作”的本质。代码量很小写完不超过五十行但里面包含的考点一个都不少闭区间的长度计算、重叠区间的合并、边界的处理、复杂度的权衡。从知识体系上看这道题至少能引出三套完全不同的解法暴力标记、差分数组、区间合并。这三种思路分别对应了“模拟思维”“端点思维”和“数学思维”后面你在做更复杂的区间问题——比如线段树覆盖、扫描线求面积、时间区间排重——时都会反复用到同一套底层逻辑。所以我觉得把这道题吃透比刷十道重复的模拟题更有价值。2. 从暴力到优雅三种解法的演进2.1 暴力标记思路最直但天花板低暴力解法没什么技巧开一个bool数组长度为L1初始全部为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[r1]上减1表示从r1开始这层影响结束。全部区间记录完之后从0到L扫一遍用一个变量current做累加。current大于0的位置说明至少被一个移除区间覆盖树被拔掉了current等于0的位置说明没有任何区间覆盖到树还在。这里有三个细节必须解释清楚。第一为什么在r1处减而不是在r处减因为区间是闭区间r上的树也要被移除所以“移除影响”必须持续到r1才终止。如果你在r处减那r这个点还没来得及被统计current就已经归零了r上的树会被误判为存活。第二diff数组要开L2的长度。因为r1最大会取到L1虽然我们扫描时只扫到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) { // 处理一组数据 }如果题目明确说“M0时结束”那就在循环里加一个判断if (L 0 M 0) break;注意这里判断的是L和M同时为0才退出。因为L0但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-1001) (471-4701) 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)这里的L2和C版里的MAXL同理都是为了防止r1越界。第三如果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::vectorstd::pairint, 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是标准做法。但这里还有一个更隐蔽的坑如果使用Pythonsys.stdin.readline()可能因为换行符或空行问题读出错误结构建议每读一行都做strip处理。另一个常见问题是在读M个区间时如果M0程序可能会访问空vector的第一个元素。我在区间合并版代码里特意加了一个M0的判断直接输出L1。这种边缘情况在样例里通常没有但不代表系统测试数据里没有。4.4 一份自查清单我把这道题容易翻车的点整理成了一张表每次写完代码按这个列表过一遍基本能保证一遍过。检查项自查方法常见错误初始树总数L1不是L少算坐标0上的树区间长度用r - l 1写成r - l差分数组大小开到L2越界访问多组输入while (scanf ! EOF)只处理一组就退出区间合并条件离散点用误用导致多算结果类型long longint溢出这张表是我做区间类题目时的通用检查模板不只是这一道题适用。凡是涉及“区间覆盖”“区间合并”的题目我都会把这几项先过一遍。5. 题目之外的延伸这套思想能用到哪5.1 线段树与扫描线的关系把“剩下的树”这道题做完之后很多人的困惑是差分数组能解决一切吗当然不能。差分数组适合“一次性把所有区间读进来最后统一查询”的静态场景。但如果区间是动态的一边修改新增一个移除区间或恢复一段树一边查询某段范围内剩余多少棵树差分数组就无能为力了。这时候就要上线段树。线段树的懒标记和区间更新本质上做的就是“区间操作”的增量记录和差分数组的核心思想一脉相承不逐个元素处理而是在区间层面记录变化。而扫描线算法更是把“端点事件”这一招发扬到了极致矩形的左边界入队时1右边界出队时-1然后扫描坐标轴和差分数组处理闹钟的例子几乎一模一样。所以说这道题不是孤立的小题它是整条算法知识链的起点。你会在这里第一次理解“端点记录变化”这件事后面学线段树、树状数组、扫描线时都会反复看到它的影子。5.2 现实场景时间区间、门店排期、日志去重这套思想在工程上的应用也很广。最常见的例子是“给定一批会议时间区间统计整个工作日里有多少分钟至少有人在开会”。把每个会议看成移除区间把时间轴看成马路把“被会议占用”看成“树被移除”问题就一模一样。差分数组可以O(分钟数 会议数)地算出每个时间点同时开会的数量比给每分钟打标记要快得多。另一个例子是门店排期。很多连锁品牌会同时下发若干条促销活动时间活动区间可能重叠门店想知道“哪些日期完全没被任何活动覆盖”。这可以直接套区间合并的代码把所有活动区间合并成互不重叠的时间段剩下的空隙就是不活动的日期。你甚至可以顺手把合并后的区间输出直接用来做备货计划。日志去重也是类似场景。比如要统计一批故障记录实际覆盖的时间范围记录之间可能重叠、可能无序合并区间后得到的就是真实影响的连续时间窗口。处理这类问题我几乎每次都直接从“剩下的树”的模板改过来改改变量名就能用。5.3 变种题求最长连续剩余段如果说“剩下的树”是区间合并的入门那有一个变种题特别适合用来检验自己是否真的掌握了不问你剩余多少棵树而是问“剩余的树中最长的连续一段有多少棵”。这个变种用暴力也能做但最优解可以直接站在区间合并的肩膀上。你先把所有移除区间合并然后计算两个相邻合并区间之间的空隙长度取最大值。注意最左端和最右端也要算左边第一段从0到第一个合并区间的左端点之前右边最后一段从最后一个合并区间的右端点之后到L。整个逻辑就是在合并区间的基础上多了一次相邻元素的差值计算代码量增加不超过十行。如果你能不看任何提示独立写出来说明你对区间合并的理解已经到位了。我一般建议刷题时用一个变种题来检验自己是不是真的理解了原题而不是背代码。写在最后的一点个人习惯这道题我自己刷了三遍。第一遍暴力模拟跑过了样例就觉得完事了第二遍学差分数组才意识到原来不用一棵一棵标树第三遍认真手写区间合并才真正搞清楚那几种边界情况为什么这么处理。说实话一遍遍重写不是因为我记性差而是每次写都会对“区间”这个概念多一层体感。最后分享一个我自己的小习惯遇到任何区间类题目先问自己三个问题——需不需要保留每一棵树的精确状态区间数量大还是坐标范围大查询是静态还是动态这三个问题的答案基本能直接指向暴力、差分、区间合并、线段树中的某一个方案。这套判断流程帮我省过很多弯路也希望你能在刷题过程中慢慢建立起自己的套路。
从“剩下的树”看区间合并与差分数组：机试高频算法详解
“KY24 剩下的树”——看到这个题号熟悉王道考研机试系列的朋友应该会心一笑。这道题几乎是所有“区间问题”的敲门砖一条马路从0铺到L每隔1米种一棵树现在给你若干个拆迁区间区间内的树全部拔掉问最后还能剩下几棵。乍一看就是个小学数学加减法但真正把它写对的人比例远比你想象的低端点算不算、区间重叠要不要去重、输入顺序乱不乱、数据范围大不大每一步都藏着坑。这篇文章我把这道题的解法、推导、实战踩坑完整梳理一遍给准备考研复试机试、算法竞赛入门以及工作中经常要和区间数据打交道的朋友做个参考。1. 先拆题这道题到底在说什么1.1 题面里的三个关键信息原题描述很简短但信息量其实不少。一条长度L的马路上从坐标0开始一直种到坐标L注意是闭区间[0, L]所以整条路上一共有L1棵树不是L棵。我第一次做这道题时就在这儿走神了潜意识里总觉得“长度是L树也是L棵”结果答案差了1排查了半天才发现是初始总数算错了。接下来是M个区间。每个区间给两个整数表示需要移除该范围内的所有树包括两个端点。这里的“包括端点”是题目里最容易被忽略的限定很多人栽跟头都是栽在这。比如区间[150, 300]意味着坐标150上的树和坐标300上的树都要拔掉它实际影响的是300 - 150 1 151棵树而不是150棵。最后一个关键信息是“区间可能重叠且输入顺序不保证”。题目不会好心地帮你把区间排好序也不会告诉你哪些区间互相覆盖。你要自己处理“同一个位置的树被多个区间重复点名”的问题。很多人在草稿纸上画线段时思路很清晰一到代码里就忘了去重导致最后被删的树被重复计算剩余数量反而偏大。1.2 为什么说它是区间处理的第一课考研机试选择这道题当开篇不是因为它难而是因为它能精确地区分一个人到底懂不懂“区间操作”的本质。代码量很小写完不超过五十行但里面包含的考点一个都不少闭区间的长度计算、重叠区间的合并、边界的处理、复杂度的权衡。从知识体系上看这道题至少能引出三套完全不同的解法暴力标记、差分数组、区间合并。这三种思路分别对应了“模拟思维”“端点思维”和“数学思维”后面你在做更复杂的区间问题——比如线段树覆盖、扫描线求面积、时间区间排重——时都会反复用到同一套底层逻辑。所以我觉得把这道题吃透比刷十道重复的模拟题更有价值。2. 从暴力到优雅三种解法的演进2.1 暴力标记思路最直但天花板低暴力解法没什么技巧开一个bool数组长度为L1初始全部为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[r1]上减1表示从r1开始这层影响结束。全部区间记录完之后从0到L扫一遍用一个变量current做累加。current大于0的位置说明至少被一个移除区间覆盖树被拔掉了current等于0的位置说明没有任何区间覆盖到树还在。这里有三个细节必须解释清楚。第一为什么在r1处减而不是在r处减因为区间是闭区间r上的树也要被移除所以“移除影响”必须持续到r1才终止。如果你在r处减那r这个点还没来得及被统计current就已经归零了r上的树会被误判为存活。第二diff数组要开L2的长度。因为r1最大会取到L1虽然我们扫描时只扫到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) { // 处理一组数据 }如果题目明确说“M0时结束”那就在循环里加一个判断if (L 0 M 0) break;注意这里判断的是L和M同时为0才退出。因为L0但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-1001) (471-4701) 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)这里的L2和C版里的MAXL同理都是为了防止r1越界。第三如果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::vectorstd::pairint, 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是标准做法。但这里还有一个更隐蔽的坑如果使用Pythonsys.stdin.readline()可能因为换行符或空行问题读出错误结构建议每读一行都做strip处理。另一个常见问题是在读M个区间时如果M0程序可能会访问空vector的第一个元素。我在区间合并版代码里特意加了一个M0的判断直接输出L1。这种边缘情况在样例里通常没有但不代表系统测试数据里没有。4.4 一份自查清单我把这道题容易翻车的点整理成了一张表每次写完代码按这个列表过一遍基本能保证一遍过。检查项自查方法常见错误初始树总数L1不是L少算坐标0上的树区间长度用r - l 1写成r - l差分数组大小开到L2越界访问多组输入while (scanf ! EOF)只处理一组就退出区间合并条件离散点用误用导致多算结果类型long longint溢出这张表是我做区间类题目时的通用检查模板不只是这一道题适用。凡是涉及“区间覆盖”“区间合并”的题目我都会把这几项先过一遍。5. 题目之外的延伸这套思想能用到哪5.1 线段树与扫描线的关系把“剩下的树”这道题做完之后很多人的困惑是差分数组能解决一切吗当然不能。差分数组适合“一次性把所有区间读进来最后统一查询”的静态场景。但如果区间是动态的一边修改新增一个移除区间或恢复一段树一边查询某段范围内剩余多少棵树差分数组就无能为力了。这时候就要上线段树。线段树的懒标记和区间更新本质上做的就是“区间操作”的增量记录和差分数组的核心思想一脉相承不逐个元素处理而是在区间层面记录变化。而扫描线算法更是把“端点事件”这一招发扬到了极致矩形的左边界入队时1右边界出队时-1然后扫描坐标轴和差分数组处理闹钟的例子几乎一模一样。所以说这道题不是孤立的小题它是整条算法知识链的起点。你会在这里第一次理解“端点记录变化”这件事后面学线段树、树状数组、扫描线时都会反复看到它的影子。5.2 现实场景时间区间、门店排期、日志去重这套思想在工程上的应用也很广。最常见的例子是“给定一批会议时间区间统计整个工作日里有多少分钟至少有人在开会”。把每个会议看成移除区间把时间轴看成马路把“被会议占用”看成“树被移除”问题就一模一样。差分数组可以O(分钟数 会议数)地算出每个时间点同时开会的数量比给每分钟打标记要快得多。另一个例子是门店排期。很多连锁品牌会同时下发若干条促销活动时间活动区间可能重叠门店想知道“哪些日期完全没被任何活动覆盖”。这可以直接套区间合并的代码把所有活动区间合并成互不重叠的时间段剩下的空隙就是不活动的日期。你甚至可以顺手把合并后的区间输出直接用来做备货计划。日志去重也是类似场景。比如要统计一批故障记录实际覆盖的时间范围记录之间可能重叠、可能无序合并区间后得到的就是真实影响的连续时间窗口。处理这类问题我几乎每次都直接从“剩下的树”的模板改过来改改变量名就能用。5.3 变种题求最长连续剩余段如果说“剩下的树”是区间合并的入门那有一个变种题特别适合用来检验自己是否真的掌握了不问你剩余多少棵树而是问“剩余的树中最长的连续一段有多少棵”。这个变种用暴力也能做但最优解可以直接站在区间合并的肩膀上。你先把所有移除区间合并然后计算两个相邻合并区间之间的空隙长度取最大值。注意最左端和最右端也要算左边第一段从0到第一个合并区间的左端点之前右边最后一段从最后一个合并区间的右端点之后到L。整个逻辑就是在合并区间的基础上多了一次相邻元素的差值计算代码量增加不超过十行。如果你能不看任何提示独立写出来说明你对区间合并的理解已经到位了。我一般建议刷题时用一个变种题来检验自己是不是真的理解了原题而不是背代码。写在最后的一点个人习惯这道题我自己刷了三遍。第一遍暴力模拟跑过了样例就觉得完事了第二遍学差分数组才意识到原来不用一棵一棵标树第三遍认真手写区间合并才真正搞清楚那几种边界情况为什么这么处理。说实话一遍遍重写不是因为我记性差而是每次写都会对“区间”这个概念多一层体感。最后分享一个我自己的小习惯遇到任何区间类题目先问自己三个问题——需不需要保留每一棵树的精确状态区间数量大还是坐标范围大查询是静态还是动态这三个问题的答案基本能直接指向暴力、差分、区间合并、线段树中的某一个方案。这套判断流程帮我省过很多弯路也希望你能在刷题过程中慢慢建立起自己的套路。
