間軸上的前驅(qū)查詢)
P15804 這個(gè)題號掛在洛谷上名字是 GESP202603 八級 消息查找。我第一次拿到它的時(shí)候第一反應(yīng)是這題不會(huì)要寫個(gè)字符串匹配吧畢竟“消息查找”四個(gè)字里“查找”最容易被理解成全文本掃描。真正讀完題以后發(fā)現(xiàn)消息內(nèi)容一個(gè)字都不用管題目關(guān)心的只是消息的接收者、發(fā)送者和時(shí)間戳。GESP 八級把它放在這里明顯不是考字符串而是考一個(gè)更本質(zhì)的能力在大量帶時(shí)間的數(shù)據(jù)里快速定位某一條。這道題做下來給我的感覺很像一堆消息像流水一樣刷過去每個(gè)用戶都有一個(gè)自己的收件箱查詢問的是“在某個(gè)時(shí)刻之前這個(gè)用戶收到的最后一條消息是誰發(fā)的”。剝掉“消息”這層外殼剩下的就是一個(gè)非常經(jīng)典的數(shù)據(jù)結(jié)構(gòu)操作——在有序序列里找前驅(qū)。本文不打算只貼一份能過的代碼我想把從題意到算法的整個(gè)思考鏈路拆開順便把考場上容易翻車的幾個(gè)點(diǎn)也一并說清楚。1. 題意還原消息、用戶和“最后一條”到底怎么定義1.1 題目在講一個(gè)什么場景題面通常會(huì)給三類數(shù)據(jù)用戶編號、消息記錄、查詢。消息記錄可以抽象成三元組t消息產(chǎn)生的時(shí)刻a發(fā)送者編號b接收者編號每次查詢給一個(gè)用戶x和一個(gè)時(shí)刻T要求你回答在時(shí)刻T及之前用戶x收到的最后一條消息是誰發(fā)來的。如果x在此之前一條消息都沒收到就輸出-1或者題目規(guī)定的其他無解標(biāo)記。這里真正需要摳清楚的詞是“最后一條”。它不是說消息在輸入文件里排在最后而是說時(shí)間戳最大但不大于T。也就是說所有消息對用戶x而言天然構(gòu)成一條時(shí)間軸我們每次查詢都是在這條時(shí)間軸上找不超過T的最右側(cè)元素。1.2 數(shù)據(jù)范圍決定算法方向雖然題目沒有把數(shù)據(jù)范圍寫在標(biāo)題里但按 GESP 八級題目的常規(guī)規(guī)模n、m、q一般都能到2×10^5級別時(shí)間戳可以大到10^9。如果對這個(gè)量級沒有概念可以算一筆賬如果每次查詢都掃描一遍所有消息單次是O(m)q次就是O(mq)。2×10^5 × 2×10^5是4×10^10哪怕每條操作只花 1 納秒也遠(yuǎn)超任何比賽時(shí)限。所以這題絕不可能是暴力掃描?？吹健安檎摇边@個(gè)關(guān)鍵詞再看到數(shù)據(jù)范圍基本可以鎖定到二分查找。唯一要想清楚的不是“用不用二分”而是“對什么二分、在哪里二分”。1.3 為什么不能直接模擬也有同學(xué)會(huì)想我按時(shí)間順序把消息一條條塞給接收者查詢時(shí)直接輸出用戶“當(dāng)前最新”的消息不就行了嗎這個(gè)思路在單條時(shí)間線增量插入時(shí)是對的但注意查詢時(shí)刻T是任意的不是只能問“當(dāng)前最新”。如果我在處理完所有消息后再回答一個(gè)T 10的查詢而某個(gè)用戶最后一條消息發(fā)生在T 20那我必須知道10時(shí)刻之前他到底收到了什么。這意味著不能只維護(hù)一個(gè)“最新值”而要把每個(gè)用戶的消息歷史完整保留下來。保留歷史以后查詢自然就變成了“在一個(gè)有序數(shù)組中找最后一個(gè)小于等于T的位置”。一句話模擬負(fù)責(zé)維護(hù)狀態(tài)但回答不了任意歷史時(shí)刻的查詢我們需要的是能隨機(jī)訪問歷史的存儲結(jié)構(gòu)。2. 按用戶分組預(yù)處理階段把事情一次做對2.1 用 vector 數(shù)組存每個(gè)用戶的時(shí)間軸既然每個(gè)用戶都要維護(hù)一條屬于自己的消息時(shí)間軸最直接的做法就是開一個(gè)vector的數(shù)組struct Msg { long long t; // 消息時(shí)間 int from; // 發(fā)送者 int id; // 輸入編號用于時(shí)間相同時(shí)保持穩(wěn)定 }; vectorvectorMsg recv(n 1);讀入一條消息(t, a, b)的時(shí)候把它 push 到recv[b]里表示用戶b在時(shí)間t收到來自a的消息。這樣所有消息都按接收者分好了組。這個(gè)分組動(dòng)作看著簡單但它是后面所有二分查詢的基礎(chǔ)。很多人在這一步會(huì)想著用mapint, vectorMsg其實(shí)沒有必要因?yàn)橛脩艟幪柋旧砭褪沁B續(xù)的1..n用vector數(shù)組不僅能省掉哈希的常數(shù)還方便隨機(jī)訪問。2.2 分組之后要不要排序如果題目保證消息記錄按時(shí)間遞增輸入那么recv[b]內(nèi)部天然有序可以直接查詢。但競賽題里這種“好事”并不一定每次都發(fā)生穩(wěn)妥起見處理完讀入后應(yīng)該對每個(gè)用戶的 vector 按時(shí)間排序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; }); }排序的代價(jià)是O(m log m)對2×10^5條消息來說完全可接受。排序之后每個(gè)recv[i]都是一個(gè)按時(shí)間從小到大排列的數(shù)組接下來所有查詢都能用二分完成。2.3 一種更穩(wěn)妥的存儲結(jié)構(gòu)我見過有人在排序前先對消息整體排一次序再按接收者分塊。那樣并不會(huì)錯(cuò)但會(huì)讓代碼更繞。更穩(wěn)妥的結(jié)構(gòu)是直接把“時(shí)間”和“發(fā)送者”綁在一個(gè)結(jié)構(gòu)體里存進(jìn)接收者的 vector。查詢時(shí)只比較t輸出時(shí)取from。如果需要輸出消息編號而不是發(fā)送者結(jié)構(gòu)中多存一個(gè)id字段就行。不要為了省內(nèi)存把時(shí)間哈希成數(shù)組下標(biāo)時(shí)間戳范圍太大離散化反而會(huì)把T的邊界處理搞復(fù)雜。直接用long long存時(shí)間是最省心、最不容易出錯(cuò)的方案。3. 回答詢問二分前驅(qū)是核心操作3.1 upper_bound 和 lower_bound 的選擇很多初學(xué)者分不清upper_bound和lower_bound。這里只需要記住一個(gè)判斷標(biāo)準(zhǔn)我們找的是“小于等于T的消息”所以要用upper_bound找到第一個(gè)大于T的位置然后往前退一位。lower_bound(T)第一個(gè)大于等于T的位置upper_bound(T)第一個(gè)大于T的位置如果T恰好等于某條消息的時(shí)間我們要的是這條消息本身所以用upper_bound(T)能把它包含進(jìn)來如果退而求其次用lower_bound(T)可能就會(huì)錯(cuò)誤地把時(shí)間等于T的那條消息漏掉。不過為了把“時(shí)間相同時(shí)多條消息”的邊界處理得更可控我更建議直接手寫二分。手寫二分的思路很直接左閉右開區(qū)間[l, r)不停把mid位置的消息時(shí)間和T比較最終l就是“第一個(gè)大于T”的位置。3.2 完整參考代碼下面這份代碼按“消息時(shí)間排序 二分前驅(qū)”的思路實(shí)現(xiàn)可以直接作為這道題的參考。#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當(dāng)v[mid].t T時(shí)說明mid位置仍然可能是答案但我們要找的是“最后一個(gè)滿足條件的”所以把左邊界往右推讓區(qū)間不斷逼近“第一個(gè)大于T的位置”。循環(huán)結(jié)束后v[l - 1]就是最后一個(gè)滿足條件的消息。如果題目要求輸出消息編號只需要把最后一行改成v[l - 1].id。如果希望查詢無解時(shí)返回0也只是一個(gè)輸出細(xì)節(jié)的區(qū)別。3.3 復(fù)雜度與空間分析預(yù)處理排序最壞O(m log m)每次查詢O(log m)總時(shí)間復(fù)雜度O(m log m q log m)空間復(fù)雜度O(n m)這個(gè)復(fù)雜度在n,m,q 2×10^5時(shí)非常穩(wěn)即使時(shí)間戳很大也只是long long比較沒有任何額外壓力。4. 從私信到群消息題目稍微變形后怎么應(yīng)對4.1 如果每個(gè)用戶關(guān)注多個(gè)群實(shí)際比賽里“消息查找”可能會(huì)被包裝成更復(fù)雜的場景用戶不一定是私信接收者而是加入若干群消息發(fā)到群里群里所有成員都能收到。這時(shí)候每個(gè)用戶收到的消息會(huì)來自多個(gè)群查詢?nèi)匀粏枴澳硞€(gè)時(shí)刻前用戶收到的最后一條消息”。如果直接按“消息復(fù)制給群里每個(gè)人”的方式建表預(yù)處理復(fù)雜度等于“每條群消息 × 這個(gè)群的人數(shù)”。只要總投遞量可控比如題目保證所有用戶關(guān)注量之和不超過2×10^5那么這種做法依然可以配合二分通過。這時(shí)每個(gè)用戶的 vector 里可能有多個(gè)來源的消息但存儲和查詢邏輯完全沒有變化讀入時(shí)把群消息復(fù)制到每個(gè)成員的收件箱排序后同一個(gè)二分代碼繼續(xù)跑。4.2 離線掃描從時(shí)間軸反過來處理如果群人數(shù)很大不能逐個(gè)復(fù)制那就不能繼續(xù)用“按用戶建時(shí)間軸”的思路了。這時(shí)候可以換一種離線做法把所有查詢按T從小到大排序。把所有消息按時(shí)間從小到大排序。用雙指針掃描每遇到一條消息就更新消息所屬群里所有成員“當(dāng)前最新消息”。這個(gè)做法對更新操作仍然有壓力所以更進(jìn)一步的優(yōu)化是把“群成員”關(guān)系做成倒排表讓每條消息只更新一次群而不是更新每個(gè)成員。最終每個(gè)查詢答案需要合并該用戶所有群里的最新狀態(tài)這時(shí)又回到了多個(gè)數(shù)組求最大值的問題可以用堆或者線段樹維護(hù)。八級考試不太會(huì)要求你現(xiàn)場寫一個(gè)復(fù)雜的可持久化結(jié)構(gòu)但“離線排序 雙指針 堆”這個(gè)套路值得掌握。它的價(jià)值在于當(dāng)你發(fā)現(xiàn)“直接復(fù)制”數(shù)據(jù)量太大時(shí)至少知道不能硬來要往離線掃描的方向想。4.3 和原題的關(guān)系別只會(huì)一種裸二分多說一句這道題叫“消息查找”不是“消息排序”也不是“消息模擬”。命題人想考察的其實(shí)是你能不能從一堆看似無序的消息里建立有序索引然后高效查詢。私信是這種思想的最小模型群消息是它的自然擴(kuò)展。把最小模型的代碼吃透再遇到擴(kuò)展版本時(shí)你只需要考慮建圖方式查詢部分完全不用重寫。5. 考場上最容易踩的四個(gè)細(xì)節(jié)5.1 時(shí)間戳范圍與類型溢出消息時(shí)間戳常常到10^9甚至更大如果不小心用int存讀入時(shí)可能已經(jīng)溢出成負(fù)數(shù)二分邏輯會(huì)直接崩掉。我的習(xí)慣是只要題目里出現(xiàn)“時(shí)間”這種可能很大的量一律用long long。這不是代碼潔癖而是避免在內(nèi)存上省 4 個(gè)字節(jié)、在調(diào)試上花 40 分鐘。5.2 空列表和越界如果某用戶一條消息都沒收到他的 vector 是空的。此時(shí)二分區(qū)間l0, r0循環(huán)不會(huì)執(zhí)行最后l0會(huì)走到“無解”分支。這個(gè)分支一定不能省否則訪問v[l-1]就是對空容器取[-1]輕則答案錯(cuò)重則直接 RE。另一種越界情況是T比該用戶所有消息時(shí)間都大。此時(shí)二分結(jié)果l等于 vector 長度輸出v[l-1]仍然安全因?yàn)閘-1是最后一個(gè)合法位置。這類邊界條件在寫代碼前最好先在草稿紙上列一遍。5.3 相同時(shí)間的多條消息怎么處理如果題目允許同一時(shí)刻一個(gè)用戶收到多條消息那“最后一條”就變得不唯一。穩(wěn)妥的做法是給每條消息保存一個(gè)輸入編號id排序時(shí)時(shí)間相同就按id升序。這樣同一時(shí)刻的多條消息也有確定的先后順序upper_bound二分的結(jié)果就是按該順序排在最后的那條。如果原題沒有做這個(gè)區(qū)分只是問“來源”而不是“哪一條消息”那排序時(shí)甚至可以不用管第二關(guān)鍵字。但在模板代碼里加上id幾乎不增加成本能避免很多隱性邊界問題。5.4 輸入輸出效率2×10^5級別的cin在關(guān)了同步之后通常沒問題但如果你還要處理多組數(shù)據(jù)或者題目數(shù)據(jù)范圍到10^6輸出用\n而不是endl能省下大量刷新緩沖的時(shí)間。endl會(huì)強(qiáng)制 flush在循環(huán)里 flush 幾萬次時(shí)間損耗非?？捎^。我建議從平時(shí)練習(xí)就養(yǎng)成習(xí)慣ios::sync_with_stdio(false); cin.tie(nullptr);寫在前三行輸出統(tǒng)一用\n。如果遇到輸入量更大的題再考慮手寫快讀但在 GESP 這個(gè)級別的題目里cin優(yōu)化后一般夠用。6. 從這道題反推 GESP 八級的出題思路6.1 一個(gè)生活化場景套一個(gè)經(jīng)典算法GESP 八級的題很喜歡做一件事把算法塞進(jìn)一個(gè)看起來和生活很近的場景里。比如“消息查找”聽起來像社交軟件的需求實(shí)際上考的是二分“商品交易”聽起來像買賣問題實(shí)際上可能是動(dòng)態(tài)規(guī)劃。這要求我們不能被題目背景帶偏看到題面先習(xí)慣性劃掉修飾詞抽出核心數(shù)據(jù)結(jié)構(gòu)和操作。這道題的核心操作就是“有序數(shù)組上的前驅(qū)查詢”。只要你識別出這一點(diǎn)后面的代碼寫起來非?？熳R別不出來就會(huì)被“查找”兩個(gè)字帶著去寫各種花哨的字符串匹配、哈希匹配最后浪費(fèi)大量時(shí)間。6.2 備考時(shí)值得做的同類題如果想針對這類“先排序再二分查詢”的題型練手可以重點(diǎn)做幾類題在數(shù)組中找某個(gè)數(shù)的第一個(gè)/最后一個(gè)位置給定若干區(qū)間統(tǒng)計(jì)某個(gè)區(qū)間內(nèi)滿足條件的數(shù)按時(shí)間排序后離線回答歷史狀態(tài)類問題建立索引后對多個(gè)列表做合并查詢這些題和“消息查找”的底層模型非常像先預(yù)處理出有序結(jié)構(gòu)再用二分快速定位。練的時(shí)候不要只背upper_bound的寫法要能徒手寫出左閉右開的手寫二分因?yàn)楹芏嘧兎N題里直接套庫函數(shù)反而要處理奇怪的邊界。6.3 一點(diǎn)個(gè)人建議我個(gè)人的體會(huì)是像“消息查找”這種題真正拉開差距的地方不在二分本身而在能不能把題意轉(zhuǎn)換成“對哪個(gè)數(shù)組做二分”。很多時(shí)候你在考場上卡住不是因?yàn)椴粫?huì)upper_bound而是因?yàn)闆]想清楚每個(gè)用戶的消息歷史應(yīng)該存在哪里。如果你現(xiàn)在準(zhǔn)備 GESP 八級建議把這類“排序 二分 離線查詢”的組合當(dāng)成本能反應(yīng)。拿到題先畫數(shù)據(jù)流輸入是什么要回答什么中間能不能建立索引。索引建出來查找就是水到渠成的事。P15804 這道題并不需要什么高深算法但它足夠檢驗(yàn)一個(gè)人是否真的理解了“查找”的本質(zhì)。 消息查找算法解析：二分查找與有序時(shí)間軸上的前驅(qū)查詢
P15804 這個(gè)題號掛在洛谷上名字是 GESP202603 八級 消息查找。我第一次拿到它的時(shí)候第一反應(yīng)是這題不會(huì)要寫個(gè)字符串匹配吧畢竟“消息查找”四個(gè)字里“查找”最容易被理解成全文本掃描。真正讀完題以后發(fā)現(xiàn)消息內(nèi)容一個(gè)字都不用管題目關(guān)心的只是消息的接收者、發(fā)送者和時(shí)間戳。GESP 八級把它放在這里明顯不是考字符串而是考一個(gè)更本質(zhì)的能力在大量帶時(shí)間的數(shù)據(jù)里快速定位某一條。這道題做下來給我的感覺很像一堆消息像流水一樣刷過去每個(gè)用戶都有一個(gè)自己的收件箱查詢問的是“在某個(gè)時(shí)刻之前這個(gè)用戶收到的最后一條消息是誰發(fā)的”。剝掉“消息”這層外殼剩下的就是一個(gè)非常經(jīng)典的數(shù)據(jù)結(jié)構(gòu)操作——在有序序列里找前驅(qū)。本文不打算只貼一份能過的代碼我想把從題意到算法的整個(gè)思考鏈路拆開順便把考場上容易翻車的幾個(gè)點(diǎn)也一并說清楚。1. 題意還原消息、用戶和“最后一條”到底怎么定義1.1 題目在講一個(gè)什么場景題面通常會(huì)給三類數(shù)據(jù)用戶編號、消息記錄、查詢。消息記錄可以抽象成三元組t消息產(chǎn)生的時(shí)刻a發(fā)送者編號b接收者編號每次查詢給一個(gè)用戶x和一個(gè)時(shí)刻T要求你回答在時(shí)刻T及之前用戶x收到的最后一條消息是誰發(fā)來的。如果x在此之前一條消息都沒收到就輸出-1或者題目規(guī)定的其他無解標(biāo)記。這里真正需要摳清楚的詞是“最后一條”。它不是說消息在輸入文件里排在最后而是說時(shí)間戳最大但不大于T。也就是說所有消息對用戶x而言天然構(gòu)成一條時(shí)間軸我們每次查詢都是在這條時(shí)間軸上找不超過T的最右側(cè)元素。1.2 數(shù)據(jù)范圍決定算法方向雖然題目沒有把數(shù)據(jù)范圍寫在標(biāo)題里但按 GESP 八級題目的常規(guī)規(guī)模n、m、q一般都能到2×10^5級別時(shí)間戳可以大到10^9。如果對這個(gè)量級沒有概念可以算一筆賬如果每次查詢都掃描一遍所有消息單次是O(m)q次就是O(mq)。2×10^5 × 2×10^5是4×10^10哪怕每條操作只花 1 納秒也遠(yuǎn)超任何比賽時(shí)限。所以這題絕不可能是暴力掃描?？吹健安檎摇边@個(gè)關(guān)鍵詞再看到數(shù)據(jù)范圍基本可以鎖定到二分查找。唯一要想清楚的不是“用不用二分”而是“對什么二分、在哪里二分”。1.3 為什么不能直接模擬也有同學(xué)會(huì)想我按時(shí)間順序把消息一條條塞給接收者查詢時(shí)直接輸出用戶“當(dāng)前最新”的消息不就行了嗎這個(gè)思路在單條時(shí)間線增量插入時(shí)是對的但注意查詢時(shí)刻T是任意的不是只能問“當(dāng)前最新”。如果我在處理完所有消息后再回答一個(gè)T 10的查詢而某個(gè)用戶最后一條消息發(fā)生在T 20那我必須知道10時(shí)刻之前他到底收到了什么。這意味著不能只維護(hù)一個(gè)“最新值”而要把每個(gè)用戶的消息歷史完整保留下來。保留歷史以后查詢自然就變成了“在一個(gè)有序數(shù)組中找最后一個(gè)小于等于T的位置”。一句話模擬負(fù)責(zé)維護(hù)狀態(tài)但回答不了任意歷史時(shí)刻的查詢我們需要的是能隨機(jī)訪問歷史的存儲結(jié)構(gòu)。2. 按用戶分組預(yù)處理階段把事情一次做對2.1 用 vector 數(shù)組存每個(gè)用戶的時(shí)間軸既然每個(gè)用戶都要維護(hù)一條屬于自己的消息時(shí)間軸最直接的做法就是開一個(gè)vector的數(shù)組struct Msg { long long t; // 消息時(shí)間 int from; // 發(fā)送者 int id; // 輸入編號用于時(shí)間相同時(shí)保持穩(wěn)定 }; vectorvectorMsg recv(n 1);讀入一條消息(t, a, b)的時(shí)候把它 push 到recv[b]里表示用戶b在時(shí)間t收到來自a的消息。這樣所有消息都按接收者分好了組。這個(gè)分組動(dòng)作看著簡單但它是后面所有二分查詢的基礎(chǔ)。很多人在這一步會(huì)想著用mapint, vectorMsg其實(shí)沒有必要因?yàn)橛脩艟幪柋旧砭褪沁B續(xù)的1..n用vector數(shù)組不僅能省掉哈希的常數(shù)還方便隨機(jī)訪問。2.2 分組之后要不要排序如果題目保證消息記錄按時(shí)間遞增輸入那么recv[b]內(nèi)部天然有序可以直接查詢。但競賽題里這種“好事”并不一定每次都發(fā)生穩(wěn)妥起見處理完讀入后應(yīng)該對每個(gè)用戶的 vector 按時(shí)間排序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; }); }排序的代價(jià)是O(m log m)對2×10^5條消息來說完全可接受。排序之后每個(gè)recv[i]都是一個(gè)按時(shí)間從小到大排列的數(shù)組接下來所有查詢都能用二分完成。2.3 一種更穩(wěn)妥的存儲結(jié)構(gòu)我見過有人在排序前先對消息整體排一次序再按接收者分塊。那樣并不會(huì)錯(cuò)但會(huì)讓代碼更繞。更穩(wěn)妥的結(jié)構(gòu)是直接把“時(shí)間”和“發(fā)送者”綁在一個(gè)結(jié)構(gòu)體里存進(jìn)接收者的 vector。查詢時(shí)只比較t輸出時(shí)取from。如果需要輸出消息編號而不是發(fā)送者結(jié)構(gòu)中多存一個(gè)id字段就行。不要為了省內(nèi)存把時(shí)間哈希成數(shù)組下標(biāo)時(shí)間戳范圍太大離散化反而會(huì)把T的邊界處理搞復(fù)雜。直接用long long存時(shí)間是最省心、最不容易出錯(cuò)的方案。3. 回答詢問二分前驅(qū)是核心操作3.1 upper_bound 和 lower_bound 的選擇很多初學(xué)者分不清upper_bound和lower_bound。這里只需要記住一個(gè)判斷標(biāo)準(zhǔn)我們找的是“小于等于T的消息”所以要用upper_bound找到第一個(gè)大于T的位置然后往前退一位。lower_bound(T)第一個(gè)大于等于T的位置upper_bound(T)第一個(gè)大于T的位置如果T恰好等于某條消息的時(shí)間我們要的是這條消息本身所以用upper_bound(T)能把它包含進(jìn)來如果退而求其次用lower_bound(T)可能就會(huì)錯(cuò)誤地把時(shí)間等于T的那條消息漏掉。不過為了把“時(shí)間相同時(shí)多條消息”的邊界處理得更可控我更建議直接手寫二分。手寫二分的思路很直接左閉右開區(qū)間[l, r)不停把mid位置的消息時(shí)間和T比較最終l就是“第一個(gè)大于T”的位置。3.2 完整參考代碼下面這份代碼按“消息時(shí)間排序 二分前驅(qū)”的思路實(shí)現(xiàn)可以直接作為這道題的參考。#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當(dāng)v[mid].t T時(shí)說明mid位置仍然可能是答案但我們要找的是“最后一個(gè)滿足條件的”所以把左邊界往右推讓區(qū)間不斷逼近“第一個(gè)大于T的位置”。循環(huán)結(jié)束后v[l - 1]就是最后一個(gè)滿足條件的消息。如果題目要求輸出消息編號只需要把最后一行改成v[l - 1].id。如果希望查詢無解時(shí)返回0也只是一個(gè)輸出細(xì)節(jié)的區(qū)別。3.3 復(fù)雜度與空間分析預(yù)處理排序最壞O(m log m)每次查詢O(log m)總時(shí)間復(fù)雜度O(m log m q log m)空間復(fù)雜度O(n m)這個(gè)復(fù)雜度在n,m,q 2×10^5時(shí)非常穩(wěn)即使時(shí)間戳很大也只是long long比較沒有任何額外壓力。4. 從私信到群消息題目稍微變形后怎么應(yīng)對4.1 如果每個(gè)用戶關(guān)注多個(gè)群實(shí)際比賽里“消息查找”可能會(huì)被包裝成更復(fù)雜的場景用戶不一定是私信接收者而是加入若干群消息發(fā)到群里群里所有成員都能收到。這時(shí)候每個(gè)用戶收到的消息會(huì)來自多個(gè)群查詢?nèi)匀粏枴澳硞€(gè)時(shí)刻前用戶收到的最后一條消息”。如果直接按“消息復(fù)制給群里每個(gè)人”的方式建表預(yù)處理復(fù)雜度等于“每條群消息 × 這個(gè)群的人數(shù)”。只要總投遞量可控比如題目保證所有用戶關(guān)注量之和不超過2×10^5那么這種做法依然可以配合二分通過。這時(shí)每個(gè)用戶的 vector 里可能有多個(gè)來源的消息但存儲和查詢邏輯完全沒有變化讀入時(shí)把群消息復(fù)制到每個(gè)成員的收件箱排序后同一個(gè)二分代碼繼續(xù)跑。4.2 離線掃描從時(shí)間軸反過來處理如果群人數(shù)很大不能逐個(gè)復(fù)制那就不能繼續(xù)用“按用戶建時(shí)間軸”的思路了。這時(shí)候可以換一種離線做法把所有查詢按T從小到大排序。把所有消息按時(shí)間從小到大排序。用雙指針掃描每遇到一條消息就更新消息所屬群里所有成員“當(dāng)前最新消息”。這個(gè)做法對更新操作仍然有壓力所以更進(jìn)一步的優(yōu)化是把“群成員”關(guān)系做成倒排表讓每條消息只更新一次群而不是更新每個(gè)成員。最終每個(gè)查詢答案需要合并該用戶所有群里的最新狀態(tài)這時(shí)又回到了多個(gè)數(shù)組求最大值的問題可以用堆或者線段樹維護(hù)。八級考試不太會(huì)要求你現(xiàn)場寫一個(gè)復(fù)雜的可持久化結(jié)構(gòu)但“離線排序 雙指針 堆”這個(gè)套路值得掌握。它的價(jià)值在于當(dāng)你發(fā)現(xiàn)“直接復(fù)制”數(shù)據(jù)量太大時(shí)至少知道不能硬來要往離線掃描的方向想。4.3 和原題的關(guān)系別只會(huì)一種裸二分多說一句這道題叫“消息查找”不是“消息排序”也不是“消息模擬”。命題人想考察的其實(shí)是你能不能從一堆看似無序的消息里建立有序索引然后高效查詢。私信是這種思想的最小模型群消息是它的自然擴(kuò)展。把最小模型的代碼吃透再遇到擴(kuò)展版本時(shí)你只需要考慮建圖方式查詢部分完全不用重寫。5. 考場上最容易踩的四個(gè)細(xì)節(jié)5.1 時(shí)間戳范圍與類型溢出消息時(shí)間戳常常到10^9甚至更大如果不小心用int存讀入時(shí)可能已經(jīng)溢出成負(fù)數(shù)二分邏輯會(huì)直接崩掉。我的習(xí)慣是只要題目里出現(xiàn)“時(shí)間”這種可能很大的量一律用long long。這不是代碼潔癖而是避免在內(nèi)存上省 4 個(gè)字節(jié)、在調(diào)試上花 40 分鐘。5.2 空列表和越界如果某用戶一條消息都沒收到他的 vector 是空的。此時(shí)二分區(qū)間l0, r0循環(huán)不會(huì)執(zhí)行最后l0會(huì)走到“無解”分支。這個(gè)分支一定不能省否則訪問v[l-1]就是對空容器取[-1]輕則答案錯(cuò)重則直接 RE。另一種越界情況是T比該用戶所有消息時(shí)間都大。此時(shí)二分結(jié)果l等于 vector 長度輸出v[l-1]仍然安全因?yàn)閘-1是最后一個(gè)合法位置。這類邊界條件在寫代碼前最好先在草稿紙上列一遍。5.3 相同時(shí)間的多條消息怎么處理如果題目允許同一時(shí)刻一個(gè)用戶收到多條消息那“最后一條”就變得不唯一。穩(wěn)妥的做法是給每條消息保存一個(gè)輸入編號id排序時(shí)時(shí)間相同就按id升序。這樣同一時(shí)刻的多條消息也有確定的先后順序upper_bound二分的結(jié)果就是按該順序排在最后的那條。如果原題沒有做這個(gè)區(qū)分只是問“來源”而不是“哪一條消息”那排序時(shí)甚至可以不用管第二關(guān)鍵字。但在模板代碼里加上id幾乎不增加成本能避免很多隱性邊界問題。5.4 輸入輸出效率2×10^5級別的cin在關(guān)了同步之后通常沒問題但如果你還要處理多組數(shù)據(jù)或者題目數(shù)據(jù)范圍到10^6輸出用\n而不是endl能省下大量刷新緩沖的時(shí)間。endl會(huì)強(qiáng)制 flush在循環(huán)里 flush 幾萬次時(shí)間損耗非?？捎^。我建議從平時(shí)練習(xí)就養(yǎng)成習(xí)慣ios::sync_with_stdio(false); cin.tie(nullptr);寫在前三行輸出統(tǒng)一用\n。如果遇到輸入量更大的題再考慮手寫快讀但在 GESP 這個(gè)級別的題目里cin優(yōu)化后一般夠用。6. 從這道題反推 GESP 八級的出題思路6.1 一個(gè)生活化場景套一個(gè)經(jīng)典算法GESP 八級的題很喜歡做一件事把算法塞進(jìn)一個(gè)看起來和生活很近的場景里。比如“消息查找”聽起來像社交軟件的需求實(shí)際上考的是二分“商品交易”聽起來像買賣問題實(shí)際上可能是動(dòng)態(tài)規(guī)劃。這要求我們不能被題目背景帶偏看到題面先習(xí)慣性劃掉修飾詞抽出核心數(shù)據(jù)結(jié)構(gòu)和操作。這道題的核心操作就是“有序數(shù)組上的前驅(qū)查詢”。只要你識別出這一點(diǎn)后面的代碼寫起來非?？熳R別不出來就會(huì)被“查找”兩個(gè)字帶著去寫各種花哨的字符串匹配、哈希匹配最后浪費(fèi)大量時(shí)間。6.2 備考時(shí)值得做的同類題如果想針對這類“先排序再二分查詢”的題型練手可以重點(diǎn)做幾類題在數(shù)組中找某個(gè)數(shù)的第一個(gè)/最后一個(gè)位置給定若干區(qū)間統(tǒng)計(jì)某個(gè)區(qū)間內(nèi)滿足條件的數(shù)按時(shí)間排序后離線回答歷史狀態(tài)類問題建立索引后對多個(gè)列表做合并查詢這些題和“消息查找”的底層模型非常像先預(yù)處理出有序結(jié)構(gòu)再用二分快速定位。練的時(shí)候不要只背upper_bound的寫法要能徒手寫出左閉右開的手寫二分因?yàn)楹芏嘧兎N題里直接套庫函數(shù)反而要處理奇怪的邊界。6.3 一點(diǎn)個(gè)人建議我個(gè)人的體會(huì)是像“消息查找”這種題真正拉開差距的地方不在二分本身而在能不能把題意轉(zhuǎn)換成“對哪個(gè)數(shù)組做二分”。很多時(shí)候你在考場上卡住不是因?yàn)椴粫?huì)upper_bound而是因?yàn)闆]想清楚每個(gè)用戶的消息歷史應(yīng)該存在哪里。如果你現(xiàn)在準(zhǔn)備 GESP 八級建議把這類“排序 二分 離線查詢”的組合當(dāng)成本能反應(yīng)。拿到題先畫數(shù)據(jù)流輸入是什么要回答什么中間能不能建立索引。索引建出來查找就是水到渠成的事。P15804 這道題并不需要什么高深算法但它足夠檢驗(yàn)一個(gè)人是否真的理解了“查找”的本質(zhì)。