尧图网站开发 
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; // 输入编号用于时间相同时保持稳定 }; vectorvectorMsg recv(n 1);读入一条消息(t, a, b)的时候把它 push 到recv[b]里表示用户b在时间t收到来自a的消息。这样所有消息都按接收者分好了组。这个分组动作看着简单但它是后面所有二分查询的基础。很多人在这一步会想着用mapint, vectorMsg其实没有必要因为用户编号本身就是连续的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; vectorvectorMsg 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 vectorMsg 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 是空的。此时二分区间l0, r0循环不会执行最后l0会走到“无解”分支。这个分支一定不能省否则访问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 这道题并不需要什么高深算法但它足够检验一个人是否真的理解了“查找”的本质。 
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; // 输入编号用于时间相同时保持稳定 }; vectorvectorMsg recv(n 1);读入一条消息(t, a, b)的时候把它 push 到recv[b]里表示用户b在时间t收到来自a的消息。这样所有消息都按接收者分好了组。这个分组动作看着简单但它是后面所有二分查询的基础。很多人在这一步会想着用mapint, vectorMsg其实没有必要因为用户编号本身就是连续的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; vectorvectorMsg 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 vectorMsg 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 是空的。此时二分区间l0, r0循环不会执行最后l0会走到“无解”分支。这个分支一定不能省否则访问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 这道题并不需要什么高深算法但它足够检验一个人是否真的理解了“查找”的本质。