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