莫隊算法

莫隊算法是一種用來處理區間問題的離線算法，也就是說，它會在把所有詢問讀進來之後，再利用詢問之間的關聯性來降低運算時間，所以它在像是 IOI 這種一定要先回傳答案才可以讀下一筆詢問的比賽不能用，但大多數的比賽都可以。

莫隊算法需要用到分塊法，令一塊大小為 ，序列長為 ，總塊數為 ，塊的編號從 開始，第 個元素所在的塊是 ，詢問有 筆。

要使用莫隊算法有一個先決條件：如果已經知道 的答案，那必須要可以快速地知道 、、、 的答案，也就是把左或右界移動一個位置，令算出新答案的複雜度為 ，有時候它可能是 ，有時候會是 ，視題目要你算什麼而定，至於算不算快就自己評估。

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

pseudo code:

1
2
3
4
5
6
7
8
9
10
11
12
13

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;
}

只要把詢問的順序記下來，得出全部詢問的答案後依序輸出就好了。

再來是最重要的複雜度，乍看之下會覺得這樣一直加減加減的，一次還只移動一格，會不會太慢啊？

移動一次邊界算新答案是 ，然後左界在相同的塊中，每次詢問最多會移動 ，因為已經按照左界所在的塊排序了，排序後連續的幾個詢問左界會在同一個塊中，而換塊的話，往右換一塊最多就移動大約 次左界（從一塊的開始移到下一塊的結尾），所以總次數大約是 ，約等於 。然後左界在相同的塊時，右界會不斷往右移，因為我們剛剛是照右界位置排序，因此右界最多移動 次，總次數是 。

左界在同一塊時，每次詢問左界最多移動 次，換塊的總移動次數是 ，因此左界移動複雜度是 ，而右界移動複雜度會是 ，乘上算出新答案的複雜度 再相加，就是 。

約為 ，根據算幾不等式，如果要讓 最小，那麼就要 ，解出來會得到 ，代回去後 會變成 ，複雜度變成 ，如果 ，那複雜度甚至只有 。

帶修改

TODO

練習題

• ZeroJudge b417 - 區間眾數
• ZeroJudge d539 - 區間最大值