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 這道題并不需要什么高深算法但它足夠檢驗一個人是否真的理解了“查找”的本質。