# 進階資料結構與莫隊算法—莫隊算法 ###### tags: `108 師大附中校隊培訓` ###### wiwiho --- 一種用來處理區間問題的離線算法 ---- 在把所有詢問讀進來之後 再利用詢問之間的關聯性來降低運算時間 ---- 在像是 IOI 這種一定要先回傳答案 才可以讀下一筆詢問的比賽不能用 但大多數的比賽都可以 --- ## 接下來要用到的符號 ---- - 一塊大小為 $k$ - 序列長為 $n$ - 總塊數為 $b=\lceil \frac{n}{k} \rceil$ - 塊的編號從 $0$ 開始 - 第 $i$ 個元素所在的塊是 $\lfloor \frac{i}{k} \rfloor$ - 詢問有 $q$ 筆 --- ## 先決條件 ---- 果已經知道 $[l,r]$ 的答案 那必須要可以快速地知道 $[l,r+1]$、$[l,r-1]$、$[l+1,r]$、$[l-1,r]$ 的答案 也就是把左或右界移動一個位置 ---- 令算出新答案的複雜度為 $O(P)$ 有時候它可能是 $O(\log n)$ 有時候會是 $O(1)$ --- ## 過程 ---- 對每一筆詢問依**左界所在的塊**由小到大排序 相同的話依**右界位置**（非塊編號）由小到大排序 接著算出第一筆詢問的答案後 用移動邊界的方式來算出下一筆詢問的答案 ---- ``` array queries = 詢問們; type ans; //目前答案 void add(type v){/*...*/} //增加一個數字，算新答案 void sub(type v){/*...*/} //移除一個數字，算新答案 int l = 0, r = -1; for(Query q : queries){ //Query是一筆詢問的資料 while(r < q.右界) sub(++r); while(r > q.右界) add(r--); while(l < q.左界) sub(l++); while(l > q.左界) add(--l); q的答案 = ans; } ``` ---- 只要把詢問的順序記下來 得出全部詢問的答案後依序輸出就好了 --- ## 複雜度 ---- 移動一次邊界算新答案是 $O(P)$ ---- 左界在相同的塊中 每次詢問最多會移動 $k$ ---- 換塊的話 往右換一塊最多就移動大約 $2k$ 次左界 所以總次數大約是 $2k\lceil \frac{n}{k} \rceil$ 約等於 $n$ ---- 左界在相同的塊時 右界會不斷往右移 右界最多移動 $n$ 次 總次數是 $bn$ ---- 乘上算出新答案的複雜度 $O(P)$ 再相加 就是 $O((kq+n+bn)P)=O((kq+bn)P)$ ---- $b$ 約為 $\frac{n}{k}$ 根據算幾不等式 如果要讓 $kq+bn$ 最小 ---- $kq=\frac{n}{k}n$ 解出來會得到 $k=\frac{n}{\sqrt{q}}$ ---- 代回去後 $kq+bn$ 會變成 $n\sqrt{q}$ 複雜度變成 $O(Pn\sqrt{q})$