P5914 MOS题解：差分+前缀和+离散化搞定区间覆盖计数

打卡第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 个查询”改成“求任意时刻楼内人数最大值”，那只需要在做完前缀和之后，对离散化后的每个坐标求一个最大值就行，不需要额外写任何复杂结构。

又比如，题目如果问“哪一段时间内人数最多、且连续覆盖”，那需要在离散化后的相邻坐标之间做判断：相邻两个关键点之间不存在其他事件，所以这段区间内人数恒定。只要前缀和求出来，再扫描相邻坐标段，就能找到覆盖人数最多的完整时间段。这些变体本质上共享同一个核心：先把区间事件拆成差分标记，再通过前缀和把“每个关键时刻的人数”算出来。背模板的人往往只记住了差分数组，却忽略了这套结构能解决的范围远不止这一道题。

2. 暴力为什么不行，差分加前缀和为什么行

2.1 数据范围下的复杂度推演

先算一笔账。假设 n=100000 个人、m=100000 个查询，如果按最直接的朴素写法，每次查询都遍历所有区间做一次判断，总运算量是 n*m = 1e10。这个量级在普通 OI 的时间限制下基本不可能通过，哪怕编译器优化