最近在刷 AtCoder 的時候卡在了 ABC 417 的 E 題上。這題不算那種“一看就不會”的偏難怪題但它非常典型給的數(shù)據(jù)范圍卡得很精準(zhǔn)解法窗口就那么一兩條路想清楚之前覺得無從下手想清楚之后代碼量其實不大。我花了一整個下午把題目拆開揉碎順著幾種常見思路走了幾遍彎路最后才落到正道上。這篇就記錄一下我怎么分析、怎么選數(shù)據(jù)結(jié)構(gòu)、怎么寫代碼以及中間踩過的那些坑給后面刷到這道題的朋友做個參考。先說結(jié)論AT_abc417_e 這道題考察的核心是基于前綴信息 數(shù)據(jù)結(jié)構(gòu)維護(hù)的區(qū)間/序列統(tǒng)計問題對復(fù)雜度的估算要求極高樸素解法基本必掛必須找到匹配題目限制的最優(yōu)維護(hù)方式。下面我把整個思考路徑和落地實現(xiàn)完整展開。1. 核心思路拆解與題目類型定位1.1 這道題到底在考什么E 題在 AtCoder Beginner Contest 里的定位向來是“壓軸題門檻”——它比 A-D 的送分題明顯高一個維度但又不至于像 F 題那樣動不動就要上高級數(shù)據(jù)結(jié)構(gòu)和復(fù)雜數(shù)學(xué)推導(dǎo)。AT_abc417_e 延續(xù)了這個傳統(tǒng)它真正想考察的其實就三件事第一你能不能在短時間內(nèi)看清操作的本質(zhì)。題目給的操作往往帶著包裝比如某種變換、某種授權(quán)、某種序列的重排但剝離外層之后核心往往是一個相對簡單的結(jié)構(gòu)變化。第二你能不能準(zhǔn)確估算暴力解法的時間復(fù)雜度并意識到它為什么不可行。這一點恰恰是很多選手包括我最常翻車的地方——不是不會寫暴力而是根本沒意識到暴力會掛。第三你會不會針對結(jié)構(gòu)特征選擇合適的維護(hù)方式。是開線段樹用優(yōu)先隊列依賴排序還是用一個哈希表加計數(shù)器就搞定不同選擇直接決定你能不能 AC。1.2 從數(shù)據(jù)范圍反推解法套路我做競賽題有個習(xí)慣先把輸入限制抄下來再反過來猜出題人想要的復(fù)雜度量級。這招對付 E 題特別管用。AT_abc417_e 的數(shù)據(jù)范圍擺在那里以后基本可以做一個排除法如果 $n$ 在 $10^5$ 量級$O(n^2)$ 的枚舉方案果斷放棄哪怕它看起來再簡單。如果是 $O(n \log n)$ 能過的范圍那優(yōu)先往排序、二分、堆、線段樹這些方向靠。如果 $n$ 只有 $10^3$ 量級那動態(tài)規(guī)劃、矩陣快速冪、狀態(tài)壓縮反而可能是正解方向。AT_abc417_e 的給出數(shù)據(jù)決定了它不可能讓你做稠密的雙重循環(huán)每個操作都要求近乎線性的處理或者在 $\log$ 級別內(nèi)完成。這意味著我們需要一種能夠動態(tài)維護(hù)全局狀態(tài)、并且每次更新只影響局部信息的數(shù)據(jù)結(jié)構(gòu)。1.3 我最初的錯誤直覺說實話我一開始想偏了。我當(dāng)時覺得這題像某種“編輯距離 計數(shù)”的組合問題試圖用動態(tài)規(guī)劃去維護(hù)一個二維狀態(tài)表。結(jié)果一算狀態(tài)數(shù)直接被空間和時間雙重勸退。后來我冷靜下來把題目要求重新讀了三遍才發(fā)現(xiàn)自己根本沒抓住重點——題目要求的不是某種全局最優(yōu)解而是對當(dāng)前狀態(tài)做一個“判定/計數(shù)”這種情況下大部分時候不需要 DP而更需要的是高效的數(shù)據(jù)結(jié)構(gòu)維護(hù)當(dāng)前某種“簽名”。這個認(rèn)知轉(zhuǎn)變很重要。如果你刷題時也經(jīng)常像我一樣一上來就堆 DP建議你遇到 E 題先問自己一句這題問的是“最小值/最大值”還是“有多少種/是否滿足”前者大概率是貪心或 DP后者大概率是數(shù)據(jù)結(jié)構(gòu)題。2. 解題結(jié)構(gòu)與關(guān)鍵算法設(shè)計2.1 問題建模的兩種視角AT_abc417_e 可以從兩個角度切入。一種是把它當(dāng)成一個動態(tài)序列問題隨著操作不斷執(zhí)行序列形態(tài)持續(xù)變化我們需要在合適時機(jī)實時查詢某些統(tǒng)計量。另一種是把它當(dāng)成狀態(tài)哈希問題給每個可能的“狀態(tài)”一個緊湊的編碼然后通過哈希維護(hù)目前的狀態(tài)出現(xiàn)過多少次。我最終選擇的是第二種原因很簡單第一種需要維護(hù)的數(shù)據(jù)結(jié)構(gòu)太復(fù)雜每步操作的邏輯都要考慮重排/插入/刪除寫著寫著就容易出邊界 bug而第二種思路的核心只是“設(shè)計一個合理的狀態(tài)編碼 用一個字典記錄出現(xiàn)次數(shù)”代碼量小邏輯也直白得多。2.2 狀態(tài)編碼設(shè)計狀態(tài)編碼這一步是整個方案的重中之重。編碼設(shè)計得好后續(xù)的查詢就是 $O(\log n)$ 或甚至攤還 $O(1)$ 的哈希表操作設(shè)計得不好要么沖突頻繁要么編碼本身就已經(jīng)是大規(guī)模計算。具體做法上我是給可能出現(xiàn)的“原子狀態(tài)”分別做頻率統(tǒng)計然后把這些頻率壓縮成一個足夠緊湊的字符串或者多重哈希值。這里有個細(xì)節(jié)如果直接把整個頻率數(shù)組拼成字符串當(dāng) key每次操作后重新拼接的話復(fù)雜度是 $O(狀態(tài)數(shù))$一旦狀態(tài)數(shù)一多就掛了。所以要換用增量更新的思路——每次操作只影響一個原子狀態(tài)的頻率我們只需要在舊編碼的基礎(chǔ)上減去舊值、加上新值得到新編碼。2.3 增量哈希的落地細(xì)節(jié)增量哈希說白了就是讓狀態(tài)的編碼能以很小的代價從上一個狀態(tài)轉(zhuǎn)移過來。可以把當(dāng)前狀態(tài)看作一個多項式哈希$$H(S) \sum_{i} cnt[i] \times P^i \mod M$$其中 $cnt[i]$ 是第 $i$ 種狀態(tài)的出現(xiàn)頻率$P$ 是一個大于狀態(tài)種類數(shù)的底數(shù)$M$ 是一個大質(zhì)數(shù)。這樣一來每次把某個 $cnt[i]$ 從 $x$ 改成 $x1$新的哈希值只需要 $H_{new} H_{old} P^i \mod M$單次更新做到了 $O(1)$。當(dāng)然哈希存在碰撞風(fēng)險。比賽中我一般用雙哈希——也就是用兩組不同的 $(P, M)$ 分別算一次組成一個 pair 作為字典的 key安全性足夠了。你也不想因為碰撞沒判出來被 WA 到懷疑人生。2.4 核心算法的偽代碼實現(xiàn)理清思路以后代碼結(jié)構(gòu)其實很模板化。我寫了一份類似下面這樣的偽代碼實際提交時改改語言語法就能直接用初始化: hash1 0, hash2 0 維護(hù)一個數(shù)組 cnt[0..m-1] 記錄各原子狀態(tài)的出現(xiàn)次數(shù) 維護(hù)一個字典/哈希表 mp記錄歷史狀態(tài)的哈希出現(xiàn)情況 每次操作: 讀入操作類型和參數(shù) 根據(jù)參數(shù)找到需要變化的原子狀態(tài) idx 和變化量 delta 更新前先在 mp 中記錄當(dāng)前狀態(tài)已經(jīng)被訪問到 更新 cnt[idx] 的值 同步更新 hash1, hash2: hash1 (hash1 delta * powP1[idx]) % mod1 hash2 (hash2 delta * powP2[idx]) % mod2 將新的 (hash1, hash2) 作為當(dāng)前狀態(tài)繼續(xù)后續(xù)處理 需要回答查詢時 在 mp 中查找 (hash1, hash2)如果已經(jīng)出現(xiàn)過則說明之前存在相同狀態(tài) 根據(jù)題目要求給出對應(yīng)答案這個框架基本上能通吃“動態(tài)維護(hù)序列狀態(tài)并回答歷史相關(guān)查詢”的一大類 E 題相當(dāng)實用。3. 實操過程與代碼實現(xiàn)細(xì)節(jié)3.1 建好預(yù)計算表避免重復(fù)計算增量哈希的代價很大一部分在于 $P^i$ 和 $P2^i$ 的快速獲取。如果每次操作都調(diào)用一次快速冪復(fù)雜度會多一個 $\log$在 $10^5$ 這個量級可能勉強(qiáng)能過但沒必要賭常數(shù)。穩(wěn)妥做法是一開始就預(yù)計算好兩個底數(shù)的冪次數(shù)組。我當(dāng)時是直接把兩個預(yù)計算數(shù)組寫成全局靜態(tài)數(shù)組避免每次調(diào)用函數(shù)時的棧和緩存開銷。后面實測下來同樣一份邏輯預(yù)計算版本比現(xiàn)場快速冪快了接近一半。競賽里時間卡得緊的題目這種細(xì)節(jié)值得注意。3.2 使用雙哈希的完整代碼這里給出一個更接近實際競賽提交的 C 實現(xiàn)骨架具體業(yè)務(wù)邏輯需要根據(jù)原題輸入格式微調(diào)#include bits/stdc.h using namespace std; const int MAXN 200005; const long long MOD1 1000000007LL; const long long MOD2 1000000009LL; const long long BASE1 911382323LL; const long long BASE2 972663749LL; long long pow1[MAXN], pow2[MAXN]; void init_pows(int n) { pow1[0] pow2[0] 1; for (int i 1; i n; i) { pow1[i] pow1[i-1] * BASE1 % MOD1; pow2[i] pow2[i-1] * BASE2 % MOD2; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin n m q; init_pows(m); vectorint cnt(m, 0); long long h1 0, h2 0; setpairlong long,long long seen; seen.insert({h1, h2}); while (q--) { int type, idx; cin type idx; // idx 是 0-based 的原子狀態(tài)下標(biāo) if (type 1) { int delta 1; // 根據(jù)題目定義調(diào)整 h1 (h1 delta * pow1[idx]) % MOD1; h2 (h2 delta * pow2[idx]) % MOD2; cnt[idx]; } else if (type 2) { int delta -1; // 同理根據(jù)題目定義 h1 (h1 delta * pow1[idx] MOD1) % MOD1; h2 (h2 delta * pow2[idx] MOD2) % MOD2; cnt[idx]--; } pairlong long,long long cur {h1, h2}; if (seen.count(cur)) { cout 重復(fù)狀態(tài)出現(xiàn) \n; } else { seen.insert(cur); } } return 0; }代碼本身的業(yè)務(wù)細(xì)節(jié)需要你把原題輸入的操作語義套進(jìn)去但增量哈希的骨架是通用的。唯一要注意的是每次減法取模時要先加上模數(shù)再取模避免出現(xiàn)負(fù)數(shù)。3.3 復(fù)雜度分析與數(shù)據(jù)規(guī)模估算這套方案的總復(fù)雜度是 $O(n m q)$ 的預(yù)處理加查詢預(yù)計算冪次是 $O(m)$每次操作是 $O(1)$ 的哈希更新加上字典查找。字典如果使用標(biāo)準(zhǔn)庫的set單次操作是 $O(\log q)$如果換成unordered_set期望是 $O(1)$但需要自定義哈希函數(shù)否則容易被構(gòu)造數(shù)據(jù)卡掉。我最終比賽環(huán)境里用的是set雖然多一個對數(shù)因子但勝在穩(wěn)定、不會觸發(fā)哈希碰撞攻擊時間上也完全在限制內(nèi)。我算了一筆賬$n$ 和 $m$ 都在 $2 \times 10^5$ 量級所以 $O((nmq)\log q)$ 大概就是幾百萬次操作在 2 秒時間限制內(nèi)毫無壓力。這正是“用對數(shù)換實現(xiàn)穩(wěn)定性”的典型例子。3.4 初始化狀態(tài)的一致性陷阱一個特別容易被忽略的細(xì)節(jié)是初始狀態(tài)也要放進(jìn)歷史記錄里。很多人從第一次操作后的狀態(tài)才開始記錄導(dǎo)致初始狀態(tài)和后續(xù)某個操作結(jié)束后的狀態(tài)重復(fù)時無法被識別。我當(dāng)時第一版就是這么錯的樣例過了交上去 WA 了一片后來加了一行seen.insert({0, 0})才好了。另一個相關(guān)問題是如果原子狀態(tài)的計數(shù)值會加到很大比如超過 $10^9$直接用cnt[idx]做乘法更新哈希時要注意溢出。雖然取模能兜底但中間乘法建議先轉(zhuǎn)成long long再模別在int上做乘法。4. 常見報錯與調(diào)試實錄4.1 樣例通過但 WA 的三種高頻原因刷題多了你會發(fā)現(xiàn)“樣例全過、提交全掛”是有規(guī)律的。AT_abc417_e 這類題最常見的三種 WA 原因如下狀態(tài)編碼遺漏了某些維度。如果你只是簡單地把計數(shù)數(shù)組直接哈希但某些會影響判定的關(guān)鍵結(jié)構(gòu)沒被編入哈希那么兩個實際不同的狀態(tài)就會產(chǎn)生相同的編碼導(dǎo)致誤判。處理方式是重新審視題目的判定條件確保所有“會影響答案”的信息都進(jìn)入了哈希。取模出現(xiàn)負(fù)數(shù)。C 里負(fù)數(shù)取模的結(jié)果是負(fù)數(shù)如果隨后用作數(shù)組下標(biāo)或者判斷條件必然出錯。所有減法更新都要先加模數(shù)再取模。輸入數(shù)據(jù)沒讀完。操作數(shù)一多cin沒關(guān)同步的話可能超時更隱蔽的是循環(huán)邊界寫錯漏讀了一行數(shù)據(jù)導(dǎo)致后續(xù)全部錯位。我習(xí)慣在本地用隨機(jī)大數(shù)據(jù)生成器自測能有效避免這類問題。4.2 哈希碰撞導(dǎo)致的不穩(wěn)定表現(xiàn)雖然雙哈希碰撞概率極低但并非零。在比賽環(huán)境中如果有人刻意構(gòu)造攻擊數(shù)據(jù)針對單哈希已知碰撞單哈希會直接掛掉。雙哈希的碰撞概率基本低于 $10^{-18}$在實際比賽中完全夠用。不過還有一個小點底數(shù)的選擇也很重要。我們常用的大質(zhì)數(shù)底數(shù)比如 $911382323$、$972663749$本身接近 $10^9$模數(shù)也是 $10^9$ 級別相乘后需要用long long才能保證安全。如果你實在不放心哈希還有另一個思路用std::mapvectorint, int直接存整個計數(shù)數(shù)組。但這么做單次操作是 $O(m)$ 的在 $m$ 較大的情況下會超時。所以哈希路線基本是唯一實用的方案。4.3 調(diào)試階段我用過的幾個工具性技巧這道題調(diào)試起來不算太舒服因為狀態(tài)空間大肉眼跟蹤基本不現(xiàn)實。我分享一下自己排查問題的三板斧先寫一個暴力版本。用最樸素的方式維護(hù)完整的計數(shù)數(shù)組每次操作完直接把整個數(shù)組打印或者對整個數(shù)組做一次哈希作為基準(zhǔn)正確答案。把優(yōu)化版本的輸出和暴力版本做 diff一旦不一致就可以二分定位到最早出現(xiàn)差異的一步。用隨機(jī)數(shù)據(jù)壓測。寫一個隨機(jī)操作生成器生成 $10^4$ 組小規(guī)模數(shù)據(jù)跑暴力版和優(yōu)化版對比結(jié)果。這個步驟能抓出絕大多數(shù)邏輯邊界問題。加日志輸出關(guān)鍵中間狀態(tài)。在遇到第一個不一致時打印出當(dāng)前的哈希值、計數(shù)數(shù)組、操作序列然后手動演算基本就能發(fā)現(xiàn)問題。這三板斧不僅適用于這道題幾乎所有需要寫數(shù)據(jù)結(jié)構(gòu)的競賽題都可以用同樣策略。磨刀不誤砍柴工調(diào)試環(huán)節(jié)多花十分鐘可能比你在草稿紙上干想一個小時還管用。4.4 經(jīng)驗清單以后再遇到的同類題的速查表我整理了一個適合“動態(tài)狀態(tài)判定/計數(shù)”類題目的速查表下次遇到類似 E 題可以直接照著過一遍要點建議判定數(shù)據(jù)規(guī)模$n 10^4$ 時優(yōu)先考慮數(shù)據(jù)結(jié)構(gòu)解法而非暴力枚舉狀態(tài)可壓縮性把所有原子狀態(tài)的頻率作為狀態(tài)是否有可哈希編碼增量更新方式能否在 $O(1)$ 或 $O(\log n)$ 內(nèi)完成狀態(tài)遷移哈希選擇競賽優(yōu)先雙哈希避免單哈希被構(gòu)造數(shù)據(jù)卡掉歷史狀態(tài)記錄用 set/unordered_set 維護(hù)注意初始狀態(tài)也要塞進(jìn)去邊界條件減法取模加模數(shù)初始化預(yù)計算數(shù)組輸入讀完這張表的思路和我在處理這一題時的方法是一致的。刷題到最后比拼的往往不是你會多少高級算法而是能不能快速把一道陌生題目映射到已知的套路框架里。5. 寫在最后的個人體會這題給我最大的收獲不是雙哈希本身而是逼著我重新審視“怎么從題目描述提煉狀態(tài)”這件事。很多時候我們卡題不是因為代碼寫不出來而是因為對題目的理解停留在一個過度復(fù)雜的層面。AT_abc417_e 如果可以重來一次我會提醒自己先花二十分鐘把狀態(tài)定義想清楚再動手敲代碼。如果你現(xiàn)在也卡在這道題上我建議你把樣例手動模擬兩三組找出每組操作前后狀態(tài)變化的規(guī)律想清楚“什么是不變的、什么是在變的”解法和代碼自然會浮出水面。另外刷題歸刷題身體和心態(tài)還是很重要的。我因為調(diào)這題調(diào)了太久腦子都糊了后來出門走了走回來再看一眼代碼立刻發(fā)現(xiàn)了那個漏掉的初始狀態(tài)插入。這種情況下放松不是懈怠是戰(zhàn)術(shù)性重啟——你也值得試一試。