企业官网建设流程全解析

P15804 这个题号挂在洛谷上，名字是 GESP202603 八级 消息查找。我第一次拿到它的时候，第一反应是：这题不会要写个字符串匹配吧？毕竟“消息查找”四个字里，“查找”最容易被理解成全文本扫描。真正读完题以后发现，消息内容一个字都不用管，题目关心的只是消息的接收者、发送者和时间戳。GESP 八级把它放在这里，明显不是考字符串，而是考一个更本质的能力：在大量带时间的数据里快速定位某一条。

这道题做下来给我的感觉很像：一堆消息像流水一样刷过去，每个用户都有一个自己的收件箱，查询问的是“在某个时刻之前，这个用户收到的最后一条消息是谁发的”。剥掉“消息”这层外壳，剩下的就是一个非常经典的数据结构操作——在有序序列里找前驱。本文不打算只贴一份能过的代码，我想把从题意到算法的整个思考链路拆开，顺便把考场上容易翻车的几个点也一并说清楚。

1. 题意还原：消息、用户和“最后一条”到底怎么定义

1.1 题目在讲一个什么场景

题面通常会给三类数据：用户编号、消息记录、查询。消息记录可以抽象成三元组：

• t：消息产生的时刻
• a：发送者编号
• b：接收者编号

每次查询给一个用户x和一个时刻T，要求你回答：在时刻T及之前，用户x收到的最后一条消息是谁发来的。如果x在此之前一条消息都没收到，就输出-1或者题目规定的其他无解标记。

这里真正需要抠清楚的词是“最后一条”。它不是说消息在输入文件里排在最后，而是说时间戳最大但不大于T。也就是说，所有消息对用户x而言天然构成一条时间轴，我们每次查询都是在这条时间轴上找不超过T的最右侧元素。

1.2 数据范围决定算法方向

虽然题目没有把数据范围写在标题里，但按 GESP 八级题目的常规规模，n、m、q一般都能到2×10^5级别，时间戳可以大到10^9。如果对这个量级没有概念，可以算一笔账：

• 如果每次查询都扫描一遍所有消息，单次是O(m)，q次就是O(mq)。
• 2×10^5 × 2×10^5是4×10^10，哪怕每条操作只花 1 纳秒，也远超任何比赛时限。

所以这题绝不可能是暴力扫描。看到“查找”这个关键词，再看到数据范围，基本可以锁定到二分查找。唯一要想清楚的不是“用不用二分”，而是“对什么二分、在哪里二分”。

1.3 为什么不能直接模拟

也有同学会想：我按时间顺序把消息一条条塞给接收者，查询时直接输出用户“当前最新”的消息不就行了吗？

这个思路在单条时间线增量插入时是对的，但注意查询时刻T是任意的，不是只能问“当前最新”。如果我在处理完所有消息后再回答一个T = 10的查询，而某个用户最后一条消息发生在T = 20，那我必须知道10时刻之前他到底收到了什么。这意味着不能只维护一个“最新值”，而要把每个用户的消息历史完整保留下来。

保留历史以后，查询自然就变成了“在一个有序数组中找最后一个小于等于T的位置”。一句话：模拟负责维护状态，但回答不了任意历史时刻的查询；我们需要的是能随机访问历史的存储结构。

2. 按用户分组：预处理阶段把事情一次做对

2.1 用 vector 数组存每个用户的时间轴

既然每个用户都要维护一条属于自己的消息时间轴，最直接的做法就是开一个vector的数组：

struct Msg { long long t; // 消息时间 int from; // 发送者 int id; // 输入编号，用于时间相同时保持稳定 }; vector<vector<Msg>> recv(n + 1);

读入一条消息(t, a, b)的时候，把它 push 到recv[b]里，表示用户b在时间t收到来自a的消息。这样所有消息都按接收者分好了组。

这个分组动作看着简单，但它是后面所有二分查询的基础。很多人在这一步会想着用map<int, vector<Msg>>，其实没有必要，因为用户编号本身就是连续的1..n，用vector数组不仅能省掉哈希的常数，还方便随机访问。

2.2 分组之后要不要排序

如果题目保证消息记录按时间递增输入，那么recv[b]内部天然有序，可以直接查询。但竞赛题里这种“好事”并不一定每次都发生，稳妥起见，处理完读入后应该对每个用户的 vector 按时间排序：

for (int i = 1; i <= n; i++) { sort(recv[i].begin(), recv[i].end(), [](const Msg& a, const Msg& b) { if (a.t != b.t) return a.t < b.t; return a.id < b.id; }); }

排序的代价是O(m log m)，对2×10^5条消息来说完全可接受。排序之后，每个recv[i]都是一个按时间从小到大排列的数组，接下来所有查询都能用二分完成。

2.3 一种更稳妥的存储结构

我见过有人在排序前先对消息整体排一次序，再按接收者分块。那样并不会错，但会让代码更绕。更稳妥的结构是直接把“时间”和“发送者”绑在一个结构体里，存进接收者的 vector。查询时只比较t，输出时取from。

如果需要输出消息编号而不是发送者，结构中多存一个id字段就行。不要为了省内存把时间哈希成数组下标，时间戳范围太大，离散化反而会把T的边界处理搞复杂。直接用long long存时间，是最省心、最不容易出错的方案。

3. 回答询问：二分前驱是核心操作

3.1 upper_bound 和 lower_bound 的选择

很多初学者分不清upper_bound和lower_bound。这里只需要记住一个判断标准：我们找的是“小于等于T的消息”，所以要用upper_bound找到第一个大于T的位置，然后往前退一位。

• lower_bound(T)：第一个大于等于T的位置
• upper_bound(T)：第一个大于T的位置

如果T恰好等于某条消息的时间，我们要的是这条消息本身，所以用upper_bound(T)能把它包含进来；如果退而求其次用lower_bound(T)，可能就会错误地把时间等于T的那条消息漏掉。

不过为了把“时间相同时多条消息”的边界处理得更可控，我更建议直接手写二分。手写二分的思路很直接：左闭右开区间[l, r)，不停把mid位置的消息时间和T比较，最终l就是“第一个大于T”的位置。

3.2 完整参考代码

下面这份代码按“消息时间排序 + 二分前驱”的思路实现，可以直接作为这道题的参考。

#include <bits/stdc++.h> using namespace std; struct Msg { long long t; int from; int id; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin >> n >> m >> q; vector<vector<Msg>> recv(n + 1); for (int i = 0; i < m; i++) { long long t; int a, b; cin >> t >> a >> b; recv[b].push_back({t, a, i}); } for (int i = 1; i <= n; i++) { sort(recv[i].begin(), recv[i].end(), [](const Msg& x, const Msg& y) { if (x.t != y.t) return x.t < y.t; return x.id < y.id; }); } while (q--) { int x; long long T; cin >> x >> T; const vector<Msg>& v = recv[x]; int l = 0, r = (int)v.size(); while (l < r) { int mid = (l + r) / 2; if (v[mid].t <= T) { l = mid + 1; } else { r = mid; } } if (l == 0) { cout << -1 << '\n'; } else { cout << v[l - 1].from << '\n'; } } return 0; }

这里唯一要解释的是二分里的l = mid + 1：当v[mid].t <= T时，说明mid位置仍然可能是答案，但我们要找的是“最后一个满足条件的”，所以把左边界往右推，让区间不断逼近“第一个大于T的位置”。循环结束后，v[l - 1]就是最后一个满足条件的消息。

如果题目要求输出消息编号，只需要把最后一行改成v[l - 1].id。如果希望查询无解时返回0，也只是一个输出细节的区别。

3.3 复杂度与空间分析

• 预处理排序：最坏O(m log m)
• 每次查询：O(log m)
• 总时间复杂度：O(m log m + q log m)
• 空间复杂度：O(n + m)

这个复杂度在n,m,q = 2×10^5时非常稳，即使时间戳很大也只是long long比较，没有任何额外压力。

4. 从私信到群消息：题目稍微变形后怎么应对

4.1 如果每个用户关注多个群

实际比赛里，“消息查找”可能会被包装成更复杂的场景：用户不一定是私信接收者，而是加入若干群，消息发到群里，群里所有成员都能收到。这时候每个用户收到的消息会来自多个群，查询仍然问“某个时刻前用户收到的最后一条消息”。

如果直接按“消息复制给群里每个人”的方式建表，预处理复杂度等于“每条群消息 × 这个群的人数”。只要总投递量可控，比如题目保证所有用户关注量之和不超过2×10^5，那么这种做法依然可以配合二分通过。

这时每个用户的 vector 里可能有多个来源的消息，但存储和查询逻辑完全没有变化：读入时把群消息复制到每个成员的收件箱，排序后同一个二分代码继续跑。

4.2 离线扫描：从时间轴反过来处理

如果群人数很大，不能逐个复制，那就不能继续用“按用户建时间轴”的思路了。这时候可以换一种离线做法：

• 把所有查询按T从小到大排序。
• 把所有消息按时间从小到大排序。
• 用双指针扫描：每遇到一条消息，就更新消息所属群里所有成员“当前最新消息”。

这个做法对更新操作仍然有压力，所以更进一步的优化是把“群成员”关系做成倒排表，让每条消息只更新一次群，而不是更新每个成员。最终每个查询答案需要合并该用户所有群里的最新状态，这时又回到了多个数组求最大值的问题，可以用堆或者线段树维护。

八级考试不太会要求你现场写一个复杂的可持久化结构，但“离线排序 + 双指针 + 堆”这个套路值得掌握。它的价值在于：当你发现“直接复制”数据量太大时，至少知道不能硬来，要往离线扫描的方向想。

4.3 和原题的关系：别只会一种裸二分

多说一句，这道题叫“消息查找”，不是“消息排序”，也不是“消息模拟”。命题人想考察的，其实是你能不能从一堆看似无序的消息里建立有序索引，然后高效查询。私信是这种思想的最小模型，群消息是它的自然扩展。把最小模型的代码吃透，再遇到扩展版本时，你只需要考虑建图方式，查询部分完全不用重写。

5. 考场上最容易踩的四个细节

5.1 时间戳范围与类型溢出

消息时间戳常常到10^9甚至更大，如果不小心用int存，读入时可能已经溢出成负数，二分逻辑会直接崩掉。我的习惯是：只要题目里出现“时间”这种可能很大的量，一律用long long。这不是代码洁癖，而是避免在内存上省 4 个字节、在调试上花 40 分钟。

5.2 空列表和越界

如果某用户一条消息都没收到，他的 vector 是空的。此时二分区间l=0, r=0，循环不会执行，最后l==0会走到“无解”分支。这个分支一定不能省，否则访问v[l-1]就是对空容器取[-1]，轻则答案错，重则直接 RE。

另一种越界情况是：T比该用户所有消息时间都大。此时二分结果l等于 vector 长度，输出v[l-1]仍然安全，因为l-1是最后一个合法位置。这类边界条件在写代码前最好先在草稿纸上列一遍。

5.3 相同时间的多条消息怎么处理

如果题目允许同一时刻一个用户收到多条消息，那“最后一条”就变得不唯一。稳妥的做法是给每条消息保存一个输入编号id，排序时时间相同就按id升序。这样同一时刻的多条消息也有确定的先后顺序，upper_bound二分的结果就是按该顺序排在最后的那条。

如果原题没有做这个区分，只是问“来源”而不是“哪一条消息”，那排序时甚至可以不用管第二关键字。但在模板代码里加上id几乎不增加成本，能避免很多隐性边界问题。

5.4 输入输出效率

2×10^5级别的cin在关了同步之后通常没问题，但如果你还要处理多组数据，或者题目数据范围到10^6，输出用'\n'而不是endl能省下大量刷新缓冲的时间。endl会强制 flush，在循环里 flush 几万次，时间损耗非常可观。

我建议从平时练习就养成习惯：ios::sync_with_stdio(false); cin.tie(nullptr);写在前三行，输出统一用'\n'。如果遇到输入量更大的题，再考虑手写快读，但在 GESP 这个级别的题目里，cin优化后一般够用。

6. 从这道题反推 GESP 八级的出题思路

6.1 一个生活化场景套一个经典算法

GESP 八级的题很喜欢做一件事：把算法塞进一个看起来和生活很近的场景里。比如“消息查找”听起来像社交软件的需求，实际上考的是二分；“商品交易”听起来像买卖问题，实际上可能是动态规划。这要求我们不能被题目背景带偏，看到题面先习惯性划掉修饰词，抽出核心数据结构和操作。

这道题的核心操作就是“有序数组上的前驱查询”。只要你识别出这一点，后面的代码写起来非常快；识别不出来，就会被“查找”两个字带着去写各种花哨的字符串匹配、哈希匹配，最后浪费大量时间。

6.2 备考时值得做的同类题

如果想针对这类“先排序，再二分查询”的题型练手，可以重点做几类题：

• 在数组中找某个数的第一个/最后一个位置
• 给定若干区间，统计某个区间内满足条件的数
• 按时间排序后离线回答历史状态类问题
• 建立索引后对多个列表做合并查询

这些题和“消息查找”的底层模型非常像：先预处理出有序结构，再用二分快速定位。练的时候不要只背upper_bound的写法，要能徒手写出左闭右开的手写二分，因为很多变种题里直接套库函数反而要处理奇怪的边界。

6.3 一点个人建议

我个人的体会是，像“消息查找”这种题，真正拉开差距的地方不在二分本身，而在能不能把题意转换成“对哪个数组做二分”。很多时候你在考场上卡住，不是因为不会upper_bound，而是因为没想清楚每个用户的消息历史应该存在哪里。

如果你现在准备 GESP 八级，建议把这类“排序 + 二分 + 离线查询”的组合当成本能反应。拿到题先画数据流：输入是什么，要回答什么，中间能不能建立索引。索引建出来，查找就是水到渠成的事。P15804 这道题并不需要什么高深算法，但它足够检验一个人是否真的理解了“查找”的本质。