神秘墓后煮shi者打卡第2955天，刷题这件事已经成了我生活里的固定节奏。今天在洛谷翻题的时候，目光停在P5914 [POI 2004] MOS上，第一反应是“2004年的题，能有多难”，读完题面之后发现事情没那么简单。这道题包装了一个大楼安防的场景：楼里有若干人，每个人在某个时间段内待在大楼中，保安会挑几个时刻抽查，问每个时刻楼里到底有多少人。剥掉故事外壳，本质就是给一堆区间，做多次点查询的区间覆盖计数。
这种题型在信奥里属于典型“看着简单、实际全是坑”的一类。数据范围只要稍微拉大一点，朴素写法的循环就会直接跑到怀疑人生；想又快又稳地通过，必须用差分加前缀和，再配合离散化处理大坐标。如果你正在系统练C++、处于信奥入门到中级阶段，这道题是一个很好的训练样本：代码量不大，却把几个高频考点全串在了一起，做完之后对区间问题的理解能提升一个台阶。
1. 题目读三遍：它到底在问什么
1.1 POI 2004 的含金量
POI 是波兰信息学奥林匹克，在欧洲的OI赛事里，题目质量一直属于第一梯队，题目风格也很有辨识度：场景叙述多，模型抽出来往往很简洁。2004 年的这届比赛，放到今天来看，不少题目依然是很好的训练材料，因为那个年代的题目很少靠毒瘤卡常取胜，核心考的是建模能力和对基础算法的理解。
MOS 这一题的场景我记得并不复杂，题面先讲楼里有多少人进出，再给出一串抽查时刻，要求输出每个时刻楼内的人数。这里要注意一个习惯：竞赛题里的“时间段”到底怎么定义端点，题目文字里可能说得比较委婉，但你写代码之前必须有一个明确的数学约定，否则后面必定翻车。我一般先把题面翻译成自己能理解、能写成代码的形式，再开始想算法，这一步在长题面题目里尤其重要。
1.2 把场景翻译成数学语言
我习惯把每个人的停留时间段定义成左闭右开区间 [l_i, r_i)，意思是这个人从时刻 l_i 进入并在楼内，到时刻 r_i 离开，离开的瞬间已经不算楼内人数。那么对于一个查询时刻 t，答案就是满足 l_i <= t < r_i 的区间个数。
举个例子，假设有 3 个人，区间分别是 [1, 4)、[2, 6)、[5, 7)，查询 t=2 和 t=5：
t=2时，第一个人和第二个人都在，第三个人还没到，所以答案是 2。t=5时，第一个人已经离开，第二个人还在，第三个人已经来了，所以答案也是 2。
这个例子里最关键的是 t=4 这种情况：第一个人是 [1,4)，那么 t=4 时他应该不在楼内。如果我们把区间当成闭区间处理，就会在这里多算一个人。所以我说，先把区间端点的语义定死，整个算法才能稳定。
1.3 这题还有几种变体问法
很多同学看完这题会觉得它只是个“查询题”，实际上同一套模型能延伸出好几个版本。如果把“回答 m 个查询”改成“求任意时刻楼内人数最大值”，那只需要在做完前缀和之后，对离散化后的每个坐标求一个最大值就行，不需要额外写任何复杂结构。
又比如，题目如果问“哪一段时间内人数最多、且连续覆盖”，那需要在离散化后的相邻坐标之间做判断：相邻两个关键点之间不存在其他事件，所以这段区间内人数恒定。只要前缀和求出来，再扫描相邻坐标段，就能找到覆盖人数最多的完整时间段。这些变体本质上共享同一个核心：先把区间事件拆成差分标记，再通过前缀和把“每个关键时刻的人数”算出来。背模板的人往往只记住了差分数组，却忽略了这套结构能解决的范围远不止这一道题。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 暴力为什么不行，差分加前缀和为什么行
2.1 数据范围下的复杂度推演
先算一笔账。假设 n=100000 个人、m=100000 个查询，如果按最直接的朴素写法，每次查询都遍历所有区间做一次判断，总运算量是 n*m = 1e10。这个量级在普通 OI 的时间限制下基本不可能通过，哪怕编译器优化再激进，哪怕数据随机且可以提前剪枝，依然有超时风险。
更难处理的是坐标范围。如果每个人的进出时刻能到 1e9，你就不能直接开一个长度为 1e9+1 的数组来做差分覆盖，内存直接爆掉。这就意味着：光知道“差分数组可以解决区间覆盖计数”还不够，还得先解决坐标太稀疏的问题。思路有两步：第一步，只在事件发生的位置(左端点、右端点、查询点)记录人数的变化；第二步，把这些关键坐标压紧成连续的编号，再在上面做前缀和。这两步合起来，就是离散化加差分。
2.2 差分数组到底在做什么
差分的本质，可以类比成商场门口统计客流。一个人在 8:00 进门，保安就在计数表上写“8:00 加 1”；他 18:00 离开，保安就在“18:00 减 1”。从早上开始把每个时刻的增减量累加起来，每个时刻得到的就是当前商场里的人数。
区间 [l, r) 也是同样的道理：在 l 处记一个 +1，在 r 处记一个 -1，最后从头做一趟前缀和。这里最容易出错的地方是：-1 到底打在 r 还是 r+1？因为我们采用的是左闭右开区间，人会在时刻 r 离开，所以 -1 必须打在 r 这个坐标上。这样查询 t=r 时，前缀和已经把这个离开的人减掉了，答案恰好正确；查询 t=r-1 时，这个 -1 还没有被加进来，所以人还在楼内。
如果题目给你的原始定义是闭区间 [l, r]，那么 -1 就得放在 r+1 这个坐标上。我自己在练习时吃过这个亏，代码能通过样例，但一到边界数据就错一位，排查了大半天才发现是端点语义没有统一。所以建议你从读题开始就固定采用左闭右开，并亲手验证第一个样例，确认题面的语义和我们一致。
2.3 离散化：把稀疏的大坐标压紧凑
坐标范围大到 1e9 时，中间有大量坐标根本没有事件发生，人数在这些空坐标上是完全不变的。对每一个整数坐标都做前缀和，既不现实，也没必要。
离散化的做法是：把所有可能出现的关键坐标收集起来，包括每个人的左端点、右端点、所有查询时刻，放入一个数组，排序去重，然后通过二分查找把每个原坐标映射为 1 到 K 之间的密集下标。这样，我们只需要在一个长度不超过 2*n + m 的数组上做差分与前缀和。为什么查询时刻也要提前加进坐标表？因为我们需要对查询点做精确的前缀和查询，如果这个坐标不在离散化表里，二分查找就找不到对应位置，答案也就无从谈起。这是新手最容易漏掉的一步。
3. C++ 实现：一份可以直接抄的模板
3.1 先想清楚再动手：变量与数据结构
动笔之前，先把需要的容器列清楚，避免写一半逻辑混乱。我从头到尾只用四个结构：
xs：离散化坐标表，存所有左端点、右端点和查询点，排序去重后使用。L、R：两个数组，分别存每个人时间段的左端点和右端点。Q：查询数组，存所有抽查时刻。diff：差分数组，大小是xs.size() + 2，用于记录每个离散化坐标上的人数变化量。
关于数据类型，我直接用 long long。虽然很多题里坐标 1e9 用 int 也扛得住，但差分累加和坐标偏移的代码里，一旦出现 l + 1 或 r + 1 之类的运算，int 在某些边界下很容易踩到溢出风险。用 long long 省心，而且现代 64 位机器上性能差距可以忽略。
3.2 核心实现：完整 C++17 代码
下面是我调试通过的版本，采用离散化加差分前缀和的标准写法，代码注释写得很详细，方便直接参考。
cpp复制#include <bits/stdc++.h>
using namespace std;
vector<long long> xs;
// 将原坐标 x 映射为离散化后的编号(从1开始)
int getId(long long x) {
// 因为 x 必然被提前放入 xs，所以 lower_bound 一定能找到相等位置
return int(lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<long long> L(n), R(n), Q(m);
for (int i = 0; i < n; i++) {
cin >> L[i] >> R[i];
xs.push_back(L[i]);
xs.push_back(R[i]);
}
for (int i = 0; i < m; i++) {
cin >> Q[i];
xs.push_back(Q[i]); // 查询点必须参与离散化
}
// 排序去重
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
// 差分数组
vector<long long> diff(xs.size() + 2, 0);
// 区间 [L, R) 表示 L 时刻进入，R 时刻离开
// 因此在 L 处 +1，R 处 -1
for (int i = 0; i < n; i++) {
diff[getId(L[i])] += 1;
diff[getId(R[i])] -= 1;
}
// 前缀和，cur[i] 表示第 i 个离散化坐标时刻的人数
vector<long long> cur(xs.size() + 2, 0);
for (int i = 1; i <= (int)xs.size(); i++) {
cur[i] = cur[i - 1] + diff[i];
}
// 回答查询
for (int i = 0; i < m; i++) {
cout << cur[getId(Q[i])] << '\n';
}
return 0;
}
3.3 代码里的几个细节，逐一说清楚
getId 的 lower_bound 是整个代码的关键：它返回第一个不小于 x 的位置，由于 x 一定在 xs 中，这个位置就是 x 本身，所以映射一定成功。编号从 1 开始而不是从 0 开始，是为了前缀和循环里 cur[i - 1] 在 i=1 时不会访问负下标，这让代码更安全，也更符合做题习惯。
diff 数组大小设置为 xs.size() + 2，多出来的两个位置是为了防止最大编号 xs.size() 处的 -1 操作越界。虽然在本例中 getId(R[i]) 最大就是 xs.size()，数组刚好够用，但多留一个位置能避免以后修改时踩坑。
cur[i] 的意义一定是“第 i 个离散化坐标值对应时刻的人数”，而不是“第 i 个整数时刻的人数”。因为我们是把坐标压缩过的，中间那些没有事件的坐标被省略了，所以前缀和只在关键点上恢复人数。这也是为什么查询点必须放进离散化坐标表并做精确二分。
3.4 第二种写法：把所有事件放在一起扫描
如果你不想写离散化和二分，还有一个思路：把所有事件放在一个数组里，每个事件是一个二元组 (坐标, 类型)，其中类型 +1 代表有人进入、-1 代表有人离开、0 代表这里有查询。所有事件按坐标从小到大排序，然后同一坐标的事件先全部累加完，再统一记录该坐标的答案。
code复制
long long cur = 0;
sort(events.begin(), events.end());
for (int i = 0; i < (int)events.size(); ) {
long long x = events[i].first;
long long delta = 0;
bool hasQuery = false;
while (i < (int)events.size() && events[i].first == x) {
if (events[i].second == 0) hasQuery = true;
else delta += events[i].second;
i++;
}
cur += delta; // 同一坐标的所有变化合并完后才更新人数
if (hasQuery) ans[x] = cur;
}
这种写法代码更短，但也更容易在“同坐标处理顺序”上出错。比如某个坐标上既有 -1 也有查询，你必须先合并 delta 再记录答案，否则会得到“离开之前”的错误人数。所以我个人更推荐标准的离散化加差分写法，思路更直观，不容易错。
4. 测试现场：从样例手算到随机对拍
4.1 手动模拟一组完整数据
口说无凭，我用一组小数据手动跑一遍。假设输入为 3 个区间和 3 个查询：
code复制3 3
1 4
2 6
5 7
2 5 7
坐标表 xs 收集全部端点与查询点：{1, 2, 4, 5, 6, 7}，排序去重后编号依次为 1 到 6。差分标记如下：
| 坐标 | 编号 | diff |
|---|---|---|
| 1 | 1 | +1 |
| 2 | 2 | +1 |
| 4 | 3 | -1 |
| 5 | 4 | +1 |
| 6 | 5 | -1 |
| 7 | 6 | -1 |
做前缀和后，得到每个坐标对应时刻的人数：
| 编号 | 原坐标 | 人数 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 4 | 1 |
| 4 | 5 | 2 |
| 5 | 6 | 1 |
| 6 | 7 | 0 |
查询 t=2 对应编号 2，答案是 2；t=5 对应编号 4，答案是 2；t=7 对应编号 6，答案是 0。这个结果与之前的推理完全一致，尤其注意到 t=4 时第一个人已经离开，人数从 2 降到了 1，说明右端点 -1 的位置是正确的。
4.2 边界数据测试清单
每次写完这类题目，我习惯把下面几类边界数据跑一遍，能过滤掉绝大多数隐藏问题：
- 空区间，比如
[1, 1)：左端点和右端点相同，+1和-1落在同一个坐标点上，前缀和时正好抵消，人数不会多算。 - 查询点恰好在某个人的离开时刻，比如查询
t=4对应上面的[1,4)：答案必须不包含这个人。 - 所有区间都不覆盖某个查询点，答案应为 0。
- 只有一个区间和一个查询点，验证最简数据。
- 大量区间端点完全相同，检验差分数组累加是否正确。
这类边界数据构造成本很低，却能帮助确认区间语义有没有搞错。我见过很多人在大样例上AC，一跑到这种边界就WA，原因基本都是端点约定和题面不一致。
4.3 写一个暴力对拍，把正解焊死
对拍是检验算法正确性最朴素也最有效的手段。做法很简单：写一个完全没有优化的暴力版本，再写一个随机数据生成器，把同一份数据分别喂给暴力和正解程序，比对输出是否一致。下面是一个暴力函数的核心逻辑：
cpp复制long long brute(const vector<pair<long long, long long>>& seg, long long t) {
long long cnt = 0;
for (auto [l, r] : seg) {
if (l <= t && t < r) cnt++; // 与正解保持相同的左闭右开语义
}
return cnt;
}
然后随机生成 n <= 10、m <= 10、坐标范围在 1 到 20 之间的数据，循环跑几千组，只要有任何一组输出不一致，就说明代码需要检查。这个流程看起来很笨，但能在几分钟内帮你找出离散化漏点、端点写错、数组越界等一系列问题。我在写这题时就是靠对拍定位到了一个隐藏的 lower_bound 返回值问题，后面会细说。
5. 常见问题与避坑指南
5.1 区间开闭混用，是最大的坑
这题翻车率最高的地方就是端点定义。如果你把区间当成闭区间处理，差分里写 diff[getId(L)]++、diff[getId(R)]--，那么查询 t=R 时人会多算一个；如果原本是闭区间，你却用了左闭右开，那么 t=L 时又可能少算。解决办法只有一个：在读题阶段就通过样例确认题目的区间语义，然后全代码统一。我自己的习惯是全部转成左闭右开，并在注释里写明，避免第二天回来看代码时自己都忘了当初的约定。
5.2 查询点忘了放进离散化坐标表
这个问题发生率不低。很多初学者先把区间端点收集起来去重，然后才读入查询，或者干脆在离散化之后才把查询点加入坐标表，导致 lower_bound 找不到精确位置。此时函数会返回第一个大于 x 的位置，甚至返回 end()，输出什么就完全不可预测了。正确做法是在读入阶段就把所有查询点一并 push_back 进 xs，再排序去重。这也是我在代码里反复强调查询点必须参与离散化的原因。
5.3 unordered_map 并不是万能选择
有些同学喜欢用 unordered_map 把坐标直接映射到人数，而不是用数组加二分。在小数据下这没啥问题，但在超大数据规模下，unordered_map 的哈希冲突和常数开销可能被卡得很惨。更关键的是，如果你用 map 存结果，单个查询复杂度多一个 log，整体性能不如数组索引。保险做法还是离散化后开 vector，查询时 lower_bound 定位，整体复杂度 O((n+m)log(n+m))，非常稳定。
5.4 输入输出和长期扩展建议
老生常谈，但还是值得写进模板：cin 和 cout 要关同步，cin.tie(nullptr) 也要写。这道题的数据量不算极端，但不关同步在一些极限数据下也会有明显差距。
最后再分享一个我的扩展练习建议。做完 P5914 之后，可以顺手尝试 P1904 那种“区间覆盖变体”，或者找一找扫描线思想相关的题。不要只满足于 AC，而是故意把题目改成“求最大人数”“求覆盖次数最多的区间”“支持在线查询”等版本，逼自己想清楚每种变体该怎么复用同一套差分结构。这比盲目刷十道新题更能巩固对前缀和与离散化的理解。
对我个人而言，这道 2004 年的题目让我重新确认了一个朴素却重要的道理：很多 WA 并不是算法不会，而是区间端点这种一眼看上去不值得花时间的细节在暗中作祟。刷题打卡越久，我越发现，读题时多花三十秒把所有语义在纸上写清楚，往往比调试三十分钟更划算。希望这篇题解能帮你把差分、前缀和和离散化这套组合真正变成自己的工具箱，下次遇到同类问题，能够直接调用。