# 莫隊算法
###### tags: `Competitive Programming Note` `108 師大附中校隊培訓`

本文已停止更新，新版請至 [WiwiHo 的競程筆記](https://cp.wiwiho.me/)

[108 師大附中校隊培訓簡報](https://hackmd.io/@wiwiho/ry9AaWTcS)

莫隊算法是一種用來處理區間問題的離線算法，也就是說，它會在把所有詢問讀進來之後，再利用詢問之間的關聯性來降低運算時間，所以它在像是 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)$，視題目要你算什麼而定，至於算不算快就自己評估。

接下來是莫隊算法的過程，首先，讀入每一筆詢問，然後對每一筆詢問依**左界所在的塊**由小到大排序，相同的話依**右界位置**（非塊編號）由小到大排序，接著算出第一筆詢問的答案後，用移動邊界的方式來算出下一筆詢問的答案。

pseudo code:

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.右界) add(++r);
    while(r > q.右界) sub(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$。

左界在同一塊時，每次詢問左界最多移動 $k$ 次，換塊的總移動次數是 $n$，因此左界移動複雜度是 $O(kq+n)$，而右界移動複雜度會是 $O(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})$，如果 $O(P)=O(1)$，那複雜度甚至只有 $n\sqrt{q}$。

## 帶修改

莫隊算法除了做查詢，也可以做修改。但是我還在學。

## 練習題

- [ZeroJudge b417](https://zerojudge.tw/ShowProblem?problemid=b417) - 區間眾數
- [ZeroJudge d539](https://zerojudge.tw/ShowProblem?problemid=d539) - 區間最大值