CF1420D Rescue Nibel! 是我最近复盘次数最多的一道区间计数题。名字带点魔幻气息但模型的本质非常朴素给你一堆区间让你从中选恰好 k 个使得它们有公共交点。乍一看以为是区间贪心实际却是组合数学和扫描线的混合体卡掉了一大批人。如果你在备战算法竞赛或者想补一补扫描线、组合数取模的盲区这篇复盘应该能帮你省下不少时间。我先把话放在前面这道题不要求你求最大重叠次数也不要求你判断存不存在 k 个区间同时覆盖某个点它只要求你把“满足条件的方案数”数出来。方向错了后面写再多代码都是白搭。下面直接进入正题。1. 先把题目翻译成人话1.1 题意不是“区间求交”是“数区间组”输入长这样第一行两个整数 n 和 k接下来 n 行每行两个整数 l_i 和 r_i。n 最大能到 3e5坐标范围能到 1e9。你需要输出从 n 个区间里选出恰好 k 个区间使得这些区间的交集不为空一共有多少种选法。答案对 998244353 取模。这里有一个非常容易理解偏的点所谓交集非空是指存在至少一个实数点同时落在你选出的 k 个区间里。至于这个点是 0.5 还是 3.14159完全没有关系。这就把问题从“几何位置”拉到了“组合计数”上。很多选手第一反应是离散化 差分把每个坐标点被多少个区间覆盖算出来然后对每个覆盖深度大于等于 k 的点累加 C(cnt, k)。这个方向不是完全错但会重复计数。举个例子三个区间完全重叠成一条线段k2 时这条线段上每一个点都同时被 3 个区间覆盖。如果对每个点都加一个 C(3,2)答案早爆了。所以我们必须给每一组合法方案指定一个独一无二的“计数点”让它在整个统计过程中只被算一次。1.2 暴力做法的死穴直接枚举任意 k 个区间复杂度是 C(n,k)。n3e5 的时候哪怕 k2 都有大约 4.5e10 种组合显然跑不动。稍微聪明一点的枚举是固定一个区间作为“基准区间”再枚举其他区间和它求交集再继续凑 k 个。这种思路的复杂度通常也逃不掉 O(n^k) 或者至少 O(n^2)同样不可行。那区间问题里最常用的工具是什么扫描线。把每个区间拆成左端点和右端点两个事件从左往右扫用一个变量 cur 维护“当前位置被多少个区间覆盖”。这个变量能告诉我们如果当前坐标正好是一个左端点在把这个新区间加进统计之前已经有多少个区间覆盖了这个点。剩下的关键问题就是怎么用 cur 去算贡献才能不重不漏。2. “最大左端点”是唯一的计数锚点2.1 为什么一个交集一定能找到一个代表点任意一组选出来的 k 个区间如果它们的交集非空那么交集的左端点是谁它其实不是一个固定的坐标而是这 k 个区间左端点中的最大值。设这个最大值是 L那么这组区间里至少有一个区间的左端点恰好等于 L。接下来要证明一个关键结论L 一定落在这 k 个区间的公共交集里。因为交集非空所以存在一个实数 x 被所有选中的区间覆盖。既然每个区间都覆盖 x那每个区间的左端点都小于等于 x右端点都大于等于 x。左端点最大值 L 自然小于等于 x。同时每个区间的右端点都大于等于 x也就大于等于 L。于是对于任意一个选中的区间它的左端点小于等于 L右端点大于等于 LL 必然在这个区间内部。换句话说L 就是这组区间的一个公共点而且它还是这组区间左端点的最大值。这个结论非常重要每一组合法的 k 元组都有且只有一个最大左端点 L。即使多个区间的左端点同时等于 L这个数值本身仍然是唯一的。所以我们完全可以规定这一组方案就在 L 这个位置被计数。把计数点从“整条公共线段”压缩到一个左端点坐标上重复计数的麻烦就消失了。2.2 用代表点拆开重复计数计数的时候我们扫描到每个实际存在的左端点 L并且在遇到一个左端点恰好为 L 的区间时让这个区间充当“当前区间”。为了凑满 k 个区间我们还需要从已经“活跃”的区间里再选 k-1 个。所谓活跃区间是指已经扫到过左端点、但还没扫到右端点的区间也就是覆盖当前坐标的区间。当前区间的左端点是 L而活跃区间里的所有左端点一定都小于等于 L所以只要这些活跃区间都覆盖 L由当前区间加上它们组成的 k 元组最大左端点就精确等于 L。反过来看会不会漏。任意一个合法 k 元组设它的最大左端点是 L。这个组里可能有若干个区间的左端点都等于 L。当我们扫描到这些同左端点区间里“最靠后的那一个”时排在它前面的同 L 区间都已经加入了活跃集合而左端点小于 L 的区间因为它们也覆盖 L所以右端点都还大于等于 L没有退出也都在活跃集合里。于是把这个最靠后的 L 区间当作当前区间再从活跃集合里选出这个 k 元组的其余 k-1 个区间这一组方案就被完整地抓取了一次。又因为同一组只有唯一的最大左端点 L所以在 L 这一批重复左端点里只有最靠后的那一个能负责计数它不会重复。这里可以做一个生活化类比想象有一群人的空闲时间区间你想找 k 个人凑在一起开会。与其枚举每个可能时刻不如规定只数“最后一个进入会议室的人入场那一刻”。他入场时如果会议室里已经有 k-1 个人还没走那么这个时刻就能开成会。每个能开成的会议组合都只会对应一个“最后入场的人”所以只需要在每个人入场时数一次当前屋子里的人数即可。3. 扫描线实现计数器是怎么把区间留住的3.1 端点事件排序左端点必须优先扫描线的第一步是把所有端点放进一个数组排序。我习惯把左端点记为事件 (pos, 0)右端点记为事件 (pos, 1)。排序时按坐标从小到大坐标相同时左端点必须排在右端点前面。这个“左端点优先”不是排序洁癖而是由区间的端点包含性决定的。一个区间 [l, r] 在 r 这个坐标点上仍然是有效的区间覆盖 r但过了 r 之后就失效了。所以扫到右端点 r 时应该先把 r 这个点的统计做完再把 cur 减一。如果你把右端点排到左端点前面碰到 [l, r] 和 [r, next] 这两个区间相邻的情况时区间 [l, r] 在 r 点就被提前删掉了可它明明覆盖 r 这个点。于是后面在 r 点处理新区间时就漏掉了这个已经结束的区间答案铁定不对。我见过不少题解把事件 pair 写成 (pos, type)type 用 0 表示左端点、1 表示右端点直接利用 pair 默认排序。这不只是图省事而是规则的自然表达坐标相同的时候 0 比 1 小天然保证左端点先处理。如果你非要用 type1 表示左端点、type0 表示右端点那就必须写自定义排序很容易忘。这个坑我踩过后面调试实录里会细说。3.2 组合数预处理998244353 下的 O(1) 查询扫描过程中需要反复求 C(cur, k-1)。cur 最多到 nn 是 3e5直接每轮用乘法除法算组合数会超时而且还要处理模运算。好消息是模数 998244353 是一个大质数于是我们可以预计算阶乘和阶乘逆元把组合数查询变成 O(1)。预处理原理不复杂C(n,m) n! / (m! * (n-m)!)。在模意义下分母需要用逆元处理。根据费马小定理a^(MOD-2) ≡ a^{-1} (mod MOD)因为 998244353 是质数。所以先算 fac[0..n] 表示阶乘然后算 invfac[n] qpow(fac[n], MOD-2)再用递推 invfac[i] invfac[i1] * (i1) % MOD 倒推出所有阶乘逆元。之后查询就是 fac[n] * invfac[m] % MOD * invfac[n-m] % MOD。有个细节必须写进代码当 m 0 或者 m n 时C(n,m) 应当返回 0。这看起来是句废话但扫描线里 cur 可能比 k-1 小如果不在函数开头判断直接访问数组就会越界轻则答案错误重则运行时崩溃。不要省略这行判断。3.3 核心扫描代码与手动模拟扫描部分的核心代码非常短短到让人怀疑是不是漏了什么。用 C 写大概是这个样子long long ans 0; int cur 0; for (auto e : events) { if (e.second 0) { ans (ans C(cur, k - 1)) % MOD; cur; } else { cur--; } }这段代码能成立的前提是事件已经排好序并且左端点优先。cur 的含义始终是“当前坐标左边已经出现左端点、右边还没出现右端点的区间数量”等价于覆盖当前坐标的区间数量。遇到左端点时当前区间还没有加入统计所以 cur 数的是别的区间。C(cur, k-1) 就是在这些别的活跃区间里再挑 k-1 个和当前区间组成 k 元组这个组的最大左端点就是当前左端点。然后 cur把当前区间纳入活跃集合。遇到右端点时这个区间从此刻开始不再覆盖右侧所以 cur--。为了验证这段代码没有数错我建议自己手推一个小数据。比如三个区间分别是 [1,5]、[1,2]、[2,4]取 k2。合法组合有 [1,5] [1,2] 交集非空[1,5] [2,4] 交集非空[1,2] [2,4] 交集为 {2} 也非空一共三种。事件顺序是 (1,0) 两次、(2,0) 一次、(2,1) 一次、(4,1) 一次、(5,1) 一次。扫到第一个左端点 1 时 cur0C(0,1)0cur 变成 1第二个左端点 1 时 cur1C(1,1)1这就是 [1,5] [1,2] 这一组cur 变成 2扫到左端点 2 时 cur2C(2,1)2这就是 [2,4] 分别搭配前两个区间的两种cur 变成 3接下来右端点依次把 cur 降回 0。答案 3完美对上。4. 完整代码与复杂度分析4.1 可直接提交的 C17 代码把前面的模块拼起来我给出一个能直接提交的版本。读入用 scanf事件用 vector 存预处理阶乘逆元然后用扫描线统计答案。注意所有可能相乘的变量都开成 long long防止中间过程溢出。#include bits/stdc.h using namespace std; using ll long long; const int MOD 998244353; ll qpow(ll a, ll b) { ll res 1; while (b) { if (b 1) res res * a % MOD; a a * a % MOD; b 1; } return res; } vectorll fac, invfac; void init(int n) { fac.resize(n 1); invfac.resize(n 1); fac[0] 1; for (int i 1; i n; i) fac[i] fac[i - 1] * i % MOD; invfac[n] qpow(fac[n], MOD - 2); for (int i n - 1; i 0; i--) invfac[i] invfac[i 1] * (i 1) % MOD; } ll C(int n, int m) { if (m 0 || m n) return 0; return fac[n] * invfac[m] % MOD * invfac[n - m] % MOD; } int main() { int n, k; scanf(%d%d, n, k); vectorpairint, int events; for (int i 0; i n; i) { int l, r; scanf(%d%d, l, r); events.push_back(make_pair(l, 0)); events.push_back(make_pair(r, 1)); } sort(events.begin(), events.end()); init(n); ll ans 0; int cur 0; for (auto e : events) { if (e.second 0) { ans (ans C(cur, k - 1)) % MOD; cur; } else { cur--; } } printf(%lld\n, ans); return 0; }这段代码里sort 默认先按 first 再按 second所以坐标相同时 type0 会排在 type1 前面左端点优先的规则被自动满足。type 这个值不是随便选的它是为了让默认排序符合题目语义。4.2 另一种写法双指针 multiset除了端点事件扫描这道题还有一种同样常见的写法我建议在训练时都试一遍。先把区间按左端点排序然后用一个 multiset 维护“已经扫过左端点但右端点还没被移出”的区间右端点。遍历到当前区间时先删除 multiset 里所有小于当前 l 的右端点因为这些区间已经无法覆盖当前左端点了。然后统计 ans C(multiset.size(), k - 1)最后把当前区间的 r 插入 multiset。这个写法的好处是不用显式构造右端点事件右端点是通过删除操作来体现的。坏处是 multiset 常数比较大插入删除都是 O(log n)整体复杂度依然是 O(n log n)但实际跑起来可能比端点排序慢一些。在 3e5 的数据量下通常也能过但如果你很在意常数端点排序更稳。另外multiset 写法在删右端点时要注意迭代器的边界比事件排序更容易写出隐蔽 bug。4.3 边界条件与数据范围检查几个容易出问题的边界情况我直接列出来。k 1答案就是 n。扫描线里 C(cur, 0) 恒等于 1每个左端点贡献一次最后答案 n。不需要特判。n 1k 1events 里只有一个左端点一个右端点扫描后答案 1正确。所有区间完全相同比如 n 4k 3合法方案数应该是 C(4,3) 4。事件扫描的过程是四个相同的左端点连续出现cur 依次为 0、1、2、3贡献分别是从第 3 个左端点开始出现 C(2,2)1第 4 个左端点贡献 C(3,2)3总共 4。这个例子能很好地验证“相同左端点不需要特殊合并”的结论。区间完全不相交如果 k 2答案必然为 0。扫描线中每个左端点出现时 cur 基本为 0C(0,k-1) 也一直是 0。坐标很大1e9 完全可以用 int 存下因为排序只比较大小不需要离散化。事件总数是 2n空间也完全够用。这些边界情况我在每次提交前都会自己过一遍能显著降低 WA 的概率。5. 现场调试实录踩过的坑和排查工具5.1 坑一右端点先排序导致样例全灭我第一次写这道题的时候把事件 pair 的 type 方向搞反了左端点用 1右端点用 0然后忘了写自定义排序。结果样例直接挂掉。当时第一反应是组合数写错了调了半天才发现是扫描顺序的问题。后来我把“左端点优先”直接写进注释里 type 0 表示左端点type 1 表示右端点。从那以后我再也没犯过这个错。这个坑的本质是区间端点包含性问题。区间 [l, r] 在 r 这个点仍然有效所以右端点事件不能排在同坐标的左端点前面。如果你把右端点理解为“在 r 之后失效”而不是“在 r 时失效”那么扫描顺序自然就是先处理左端点再处理右端点。想通这一点同类问题都不容易再错。5.2 坑二组合数返回 0 的时机另一个特别常见的 bug 是 C(cur, k-1) 里 cur 比 k-1 小的时候如果函数里没有判断会访问到数组的负下标。这类错误在小数据上经常恰好不触发一到大数据就暴露。比如 k 很大而前面几个左端点附近的活跃区间很少cur 一直小于 k-1此时一旦没有边界处理程序可能直接崩掉。我建议所有组合数函数都写成这样先判断if (m 0 || m n) return 0;再计算。不要因为题目看起来保证了参数范围就省略这行尤其是扫描线里的 cur 是动态变化的你没法保证它永远不小于 k-1。5.3 坑三对拍脚本是救命稻草计数题最难受的就是“看起来对实际数多了或数少了”。我调试这种题的习惯是先用暴力枚举所有 C(n,k) 组合求出小数据下的真实答案再用扫描线跑同一组随机数据两个答案对不上就说明算法有 bug。暴力代码可以写得很短long long brute 0; for (int mask 0; mask (1 n); mask) { if (__builtin_popcount(mask) ! k) continue; int L -1, R INT_MAX, cnt 0; for (int i 0; i n; i) if (mask i 1) { L max(L, seg[i].l); R min(R, seg[i].r); cnt; } if (cnt k L R) brute; }暴力复杂度是 O(2^n)所以随机数据的 n 不能超过 15。多造几十组数据跑对拍几乎能把所有端点排序、相同坐标、k 很小的边角情况都覆盖到。我强烈建议竞赛选手掌握这个“暴力验证 算法对拍”的流程它比盯着公式看半天要高效得多。6. 从这道题能看到的一类套路6.1 区间计数题里的“代表元”思想CF1420D 解决的核心手法可以提炼成一句话如果一个计数对象有多个可计数的位置就给每个对象指定一个唯一位置这个位置通常取边界。区间问题里左端点是最自然的边界。很多类似题目都可以套这个思路。比如“从若干区间里选出 k 个要求两两有交”之类的变体第一步往往也是排序然后用某个极值点作为代表。我后来遇到一些区间计数题第一反应不再是离散化求覆盖次数而是先问自己能不能把每一组合法方案绑定到它最左边或最右边的关键点上如果能问题就变成了“对每个左端点统计它代表的方案数”然后扫描线或树状数组维护可用区间集合。这套思维在 Div2 D 和 E 里出现频率很高值得专门总结成自己的做题模板。6.2 如果再改改条件思路往哪走如果题目改成“选择的 k 个区间的交集长度至少为 X”光靠最大左端点就不够了。因为一个组的交集可能跨越多个单位长度单纯绑定到左端点 L 无法体现长度限制。这时候通常需要给交集右端点也做扫描线或者用容斥去掉长度不足的方案。复杂度会明显上升但“代表元”的思想还是主线。如果改成“选出的 k 个区间两两相交”那是另一类经典问题往往用到“不交区间计数”的容斥或者按左端点排序后用树状数组维护后缀信息。题目虽然变了但排序加维护活跃集合加组合计数的底层套路仍然是一致的。这也是为什么我不建议只背这道题的题解而要理解它背后的计数结构。最后分享一个我自己的习惯每过一道区间扫描线题我都会保存一组手算过的边界数据包括全同区间、单点区间、完全不相交三种。下次写类似题目时先用这三组数据自测一遍能省下大量提交 WA 的时间。CF1420D 这道题我至少复盘了三遍第一遍卡在排序第二遍卡在组合数越界第三遍才真正想清楚代表元。希望这篇复盘能帮你少走这几段弯路。