企业官网建设流程全解析

CF816B Karen and Coffee，这道题在算法竞赛里被分到Div2的B题，但每次带新人训练，我都会专门把它拎出来讲一次。原因很简单：它把差分数组和前缀和这两个最基础、也最容易被轻视的工具，放进了一个非常自然的场景——大量区间做覆盖统计，大量区间做查询。题面讲的是Karen的咖啡食谱，可本质上就是在问：给你一堆区间，每个点被覆盖了多少次，然后快速回答任意一段区域里满足条件的点有多少个。

不管你是刚接触算法竞赛的初学者，还是已经在刷题但区间问题总绕弯的老手，这题都值得认真拆一遍。它不仅代码量小、思路清晰，还能帮你把“差分 + 前缀和”这一套组合彻底焊死在脑子里。后面遇到类似的静态区间统计题，基本可以直接套用同一个骨架。

1. 题目拆解：Karen的咖啡温度统计到底在算什么

1.1 原题描述与输入输出格式

题目虚构了一个叫Karen的咖啡爱好者，她手上有一批咖啡食谱，每个食谱都会标注一个温度范围，表示咖啡在这个温度区间内风味最佳。现在定义一个温度是“可接受”的，条件是至少有k个食谱都推荐了这个温度。接下来有q次询问，每次给一个温度区间，问这个区间里一共有多少个温度点是可接受的。

我把题面转成更竞赛化的语言：

• 输入第一行是三个数 n、k、q，分别表示食谱数量、可接受阈值、查询次数。
• 接下来 n 行，每行两个整数 l、r，表示一个食谱推荐的温度范围，闭区间 [l, r]。
• 再接下来 q 行，每行两个整数 a、b，表示一次查询，问闭区间 [a, b] 内有多少个温度值被至少 k 个区间覆盖。
• 温度和查询里的所有值都在 1 到 200000 这个范围里。

这个 200000 的上限是整个问题的题眼。它意味着你完全可以用数组下标来表示温度值，不需要离散化，不需要平衡树，老老实实开一个长度 200000 出头的数组就够用。如果这个上限是 1e9，解法思路就要完全换一套了。

1.2 暴力解法为什么跑不动：算一笔复杂度账

新人拿到题最常见的反应是：直接对每个食谱，把它覆盖的每个温度点计数加一。看起来很直白，但我们要认真算算复杂度。

假设最坏情况下 n = 200000，每个食谱的区间都是 [1, 200000]，那么每个食谱要标记 200000 个温度点，总操作量是 200000 × 200000 = 4 × 10^10。这个数字是什么概念？一般在线评测系统 1 秒能跑大约 10^8 到 10^9 次简单运算，4 × 10^10 意味着即使常数非常小，也要几十秒才能跑完，跟常见的 2 秒时限完全不是一个量级。

就算数据没那么极端，比如每个区间平均长度是 1000，n = 200000，总操作量也是 2 × 10^8，在 C++ 里如果常数稍微大一点，同样非常危险。更别提后面还有 q 次查询，如果每次查询再遍历区间，复杂度就彻底失控了。

所以这道题的核心矛盾非常清晰：区间覆盖次数要在所有点上一遍算出来，区间查询要能 O(1) 回答。看到这个矛盾，你应该立刻联想到两个工具——差分数组负责快速记录区间覆盖，前缀和负责把覆盖次数和可接受状态变成可查询的累计值。

2. 算法核心：差分数组加两次前缀和的组合拳

2.1 差分数组：从“逐段标记”到“只记变化”

在讲算法之前，先解决一个很多人一直没彻底搞懂的问题：差分数组到底是什么，它为什么能把区间加法的复杂度降下来。

你可以把差分数组想象成一个“事件记录器”。现在我要给区间 [l, r] 内每个值都加 1，如果暴力做，就是在这段区间里一个一个加。但换成事件视角，整件事其实只有两个时间点有意义：进入这个区间的那一刻，覆盖次数开始变多；离开这个区间的那一刻，覆盖次数就要恢复原状。

于是差分数组只记录这两件事：在位置 l 记一个 +1 的事件，在位置 r+1 记一个 -1 的事件。之后我对差分数组做一次前缀和，就能还原出每个位置真实的覆盖次数。因为前缀和的本质是“把之前所有变化量累加起来”，走到 l 的时候多出来的 1 会一直跟着走，直到 r+1 位置的 -1 把它抵消掉。

用生活里的例子就是：你记录一条街上每小时的客流量变化，不用每分钟都写数字，只要记“几点钟进来了多少人、几点钟走掉了多少人”，然后顺着时间把人数累加，就能得到每个时刻店里的实际人数。差分数组干的就是这个活。

2.2 两次遍历的完整设计：覆盖次数数组加可接受前缀和

这道题需要两层处理，我习惯分两步走，思路清晰还不容易乱。

第一步，用差分数组算出每个温度被多少个食谱覆盖。

准备好差分数组 diff，长度开到 200000 + 2。每读入一个食谱区间 [l, r]，就执行 diff[l] 加 1，diff[r+1] 减 1。等所有食谱都处理完，从 1 到 200000 做一次前缀和，得到数组 cover，其中 cover[i] 表示温度 i 被多少个食谱覆盖。

第二步，把“可接受”状态转换成前缀和。

有了 cover 数组之后，定义一个标记数组 ok，如果 cover[i] 大于等于 k，说明温度 i 可接受，ok[i] = 1，否则是 0。接下来再对 ok 做一次前缀和，得到数组 pref，其中 pref[i] 表示从温度 1 到温度 i 一共有多少个可接受的温度点。

到这里，查询就变成了一个减法：区间 [a, b] 内的可接受温度数量等于 pref[b] - pref[a-1]。因为前缀和天然支持区间求和，左端点减一正好把区间前面的部分全部减掉。

2.3 为什么这是“区间覆盖统计”的通用骨架

如果只看题面，Karen and Coffee 似乎只是个普通的签到题，但它背后的模型其实出现频率非常高：先给一批区间做覆盖标记，再给一批区间做统计查询。题目换成“统计每个时间段有多少个会议在进行”“统计每段道路上被多少条公交线路覆盖”，解法完全一样。

这个模型的核心价值在于：它把“区间修改 + 区间查询”的静态问题，用一个 O(n + MAXT + q) 的算法解决掉了。这里的 MAXT 是温度值域范围，也就是 200000。更重要的是，通过两次前缀和，我们把“覆盖次数”和“可接受标记”分层处理了：第一次前缀和还原原始覆盖值，第二次前缀和把条件判断后的结果变成可查询结构。

我之所以强调这是一个通用骨架，是因为很多新生动辄就想上线段树或树状数组。但对这种静态区间问题，线段树不仅代码长，还可能因为复杂度多了个 log 而吃亏。先用差分前缀和，是性价比最高的选择。

3. 代码实现与关键细节打磨

3.1 参考实现与逐段说明

下面是我常用的 C++ 实现，代码不长，但每个细节都有讲究。

#include <bits/stdc++.h> using namespace std; const int MAXT = 200000; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k, q; cin >> n >> k >> q; vector<int> diff(MAXT + 2, 0); for (int i = 0; i < n; i++) { int l, r; cin >> l >> r; diff[l]++; diff[r + 1]--; } vector<int> cover(MAXT + 2, 0); for (int i = 1; i <= MAXT; i++) { cover[i] = cover[i - 1] + diff[i]; } vector<int> pref(MAXT + 2, 0); for (int i = 1; i <= MAXT; i++) { pref[i] = pref[i - 1] + (cover[i] >= k ? 1 : 0); } while (q--) { int a, b; cin >> a >> b; cout << pref[b] - pref[a - 1] << '\n'; } return 0; }

几个细节值得单独讲。

首先是数组大小。差分开到 MAXT + 2，表面上看只比 200000 大了 2，其实是为了防止访问 diff[r + 1] 时越界。当 r = 200000 时，r + 1 = 200001，所以数组至少要开到下标 200001。我习惯多开一点，避免各种边界审查，vector 默认初始化为 0 也省去了手动清零的麻烦。

其次是循环从 1 开始。温度值从 1 开始计数，前缀和的语义也是“从下标 1 累加到当前下标”，这样 pref[a - 1] 在 a = 1 时变成 pref[0]，正好是 0，不需要额外处理边界。

最后是输入输出加速。竞赛里 n 和 q 都是 200000，如果用默认的 cin 不关同步，读入量虽然不算特别大，但无谓的时间消耗还是能省则省。我习惯加两行 ios::sync_with_stdio(false) 和 cin.tie(nullptr)，或者直接用 scanf/printf 风格。

3.2 边界条件与下标偏移的坑

这道题代码短，但边界坑一点也不少，我见过的翻车案例能列一长串。

第一个坑是 diff[r + 1] 越界。这个问题在数组开成 200001 时最容易出现，因为 r + 1 恰好等于 200001，如果你开的是int diff[200001]，合法下标是 0 到 200000，访问 200001 直接就崩了。正确做法是开 200005 或动态 vector 开到 MAXT + 2。

第二个坑是查询公式记错。有人写 pref[b] - pref[a]，看起来差不多，但语义完全错了。pref[b] 统计的是 1 到 b 的和，pref[a] 统计的是 1 到 a 的和，两者相减得到的其实是区间 [a+1, b] 的结果，把位置 a 本身漏掉了。必须减 pref[a - 1]，才能完整包含左端点。

第三个坑是把 cover 和 pref 混在一起用。有些初学者为了省事，想一步到位：先算 cover，然后直接在 cover 上做前缀和，最后用 cover[b] - cover[a-1] 当作答案。这当然是错的，因为 cover 存的是覆盖次数，不是可接受标记。你必须先做一次条件判断，把覆盖次数转成 0/1，再对这个 0/1 序列做前缀和。

还有一个容易被忽略的点：如果题目保证所有温度值都从 1 开始，那没问题；如果哪天遇到从 0 开始的坐标，整个数组下标都要相应平移。好在 CF816B 给了从 1 开始的范围，省了这层麻烦。

3.3 复杂度与内存表现

时间复杂度分三段：读入 n 个区间做差分是 O(n)，两次前缀和遍历是 O(MAXT)，q 次查询每次 O(1)。总复杂度 O(n + MAXT + q)。把 200000 代进去，最多几十万次操作，跑起来基本就是瞬间出结果。

空间方面，diff、cover、pref 三个数组，每个长度 200005 左右，int 类型各占约 800KB，加一起只有 2.4MB 左右，完全没有压力。这也是我推荐这种做法的原因之一：不仅快，而且省。

如果硬要压缩，其实 cover 和 diff 可以复用，差分计算完后 cover 已经存了最终结果，pref 可以在 cover 的基础上继续做。但为了代码可读性，我一般不会刻意省这几个数组。竞赛里最重要的不是变量用得多干净，而是思路不糊涂。

4. 实战踩坑与排查记录

4.1 典型教训一：数组越界与运行时错误

我带过的某位同学第一次交这道题，本地测试样例全过，交上去直接 RE。查了半天，问题出在他把 diff 数组开成了int diff[200005]，然后循环读入时执行diff[r + 1]--，当 r = 200000 时访问的就是 200001。数组下标 200005 按理说是够的，但他写了if (r < 200000) diff[r + 1]--，多此一举不说，反而在边界处漏掉了减一操作。

正确的处理方式很简单：要么数组开大到 200005，然后无脑执行 diff[r + 1]--，让 200001 这个位置被正常访问；要么循环到 MAXT 时不再需要操作 diff[200001]，因为后面已经没有温度点了。我强烈建议前者，少写判断条件，也少出错。

排查这类问题的小技巧：本地编译后开 AddressSanitizer，或者直接跑一个 r = 200000 的极端样例，很容易暴露越界。很多新人不敢构造极端数据，其实竞赛里这种边界恰恰是最常出问题的位置。

4.2 典型教训二：查询公式写错

还有一个高频错误，是把查询答案写成pref[b] - pref[a]。这种错误特别隐蔽，因为样例数据往往区间左端点比较小，差 1 的结果不一定立刻体现出来。比如查询 [2, 5]，正确结果应该包含 2、3、4、5 四个点，而错误公式算的是 3、4、5 三个点。如果区间内恰好 2 和 3 状态一致，样例就察觉不到。

我自己 debug 时会专门写一个小暴力程序对照，随机生成小数据，暴力统计每个查询的答案，再跟差分前缀和的输出比对。一旦不一致，第一优先检查的永远是前缀和的减一操作和区间边界。

4.3 自测数据的构造技巧

说到自测，这里分享一个非常实用的方法：在本地写一个brute版本，也就是最简单的暴力统计版本，用来验证正解是否正确。构造数据时不要用特别大的数，比如 n 和 q 都取 20，温度范围取 50，随机生成区间。然后让暴力程序和优化程序跑同一组数据，逐行比对输出。

这种“对拍”的打法在竞赛里非常常用，尤其适合这种代码量不大但边界多的题。你不需要每次都写，但遇到思路不确定的题，花五分钟写个暴力对拍，能省下无数次错误提交的罚时。我第一次写差分数组题时就用了这个方法，后来养成了习惯，遇到区间类题目都会先搭个暴力框架做对照。

5. 题型迁移与后续进阶方向

5.1 从一维差分到二维差分

如果你把 Karen and Coffee 彻底吃透了，下一步很自然会想到二维版本：给定若干个矩形区域，每个点被覆盖了多少次，然后查询某个子矩形内满足条件的点数。这对应的是二维差分和二维前缀和。

原理和一维完全一样。差分时对矩形的四个角分别做加法或减法，前缀和时从上到下、从左到右做两轮累加。查询时也是用四个前缀和值做加减组合。很多选手在学会一维差分后，看到二维题还是会懵，其实只需要记住“事件记录”的思路不变，只是从两个事件点变成了四个事件角。

具体的四角公式是：对矩形左上角 (x1, y1) 加 1，右上角 (x1, y2+1) 减 1，左下角 (x2+1, y1) 减 1，右下角 (x2+1, y2+1) 加 1。做完四次加减小操作后，对全图做二维前缀和，每个位置就是覆盖次数。这个扩展很值得自己动手写一遍。

5.2 比赛里如何快速识别这类题

竞赛做题节奏很重要。一道 Div2 B 题，理想情况应该控制在 15 到 20 分钟内过掉，所以读题后的第一反应速度很关键。

我总结几个识别信号：题面里有“区间”“覆盖”“至少 k 次”“多次询问某一段内符合条件的数量”，这些关键词同时出现时，十有八九是差分前缀和的路子。再看一眼数据范围，如果值域是 1e5 或 2e5 这种刚好能开数组的量级，基本可以确认。

反过来，如果值域高达 1e9，开不了数组，那就要考虑离散化，把出现的左端点、右端点、查询端点全部收集起来排序去重，再在压缩后的坐标上做差分。思路还是同一套，只是坐标映射多了一步。

另外也要注意一个问题是不是带修改的。如果题目要求动态更新区间覆盖，再实时查询，那差分前缀和就撑不住了，得上树状数组或线段树。CF816B 是纯静态的，这也是它适合拿来练基础的原因。

5.3 类似模型与配套练习建议

如果想趁热打铁，可以找几道同类型的题目巩固。比如给定若干区间，问每个点被覆盖的最多次数；或者给定若干区间，问所有未被覆盖的区间长度；再或者给定若干区间和若干询问，问某个区间内有没有点没被覆盖过。这些题长得不一样，但核心都是差分或者前缀和的变体。

我自己带训练时，会给新人布置一个组合套餐：先做 CF816B 当入门，再做一道带离散化的区间覆盖题，最后上一道二维差分模板题。这个顺序下来，区间统计这块地基基本就稳了。做题时别只追求 AC，每道题都想想“如果值域变大怎么办”“如果查询变多怎么办”，把思路吃透，比刷三遍重复题型有用得多。

我个人在实际操作中最大的体会是，差分数组这种工具，单独拿出来谁都认识，难点在于遇到新题时敢不敢第一时间用它。很多人在赛场上绕了一大圈，用树状数组写了几十行，回头发现一个差分数组加前缀和就能干净利落地解决。多练几道区间覆盖题，你也会形成这种条件反射：看到静态区间统计、值域可开数组，直接上差分+前缀和，不纠结。最后再分享一个小技巧：写出代码后，把输出格式跟暴力程序对拍一遍，再交上去，稳定性和心态都会好很多。