莫隊算法

tags: Competitive Programming Note 108 師大附中校隊培訓

本文已停止更新,新版請至 WiwiHo 的競程筆記

108 師大附中校隊培訓簡報

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

莫隊算法需要用到分塊法,令一塊大小為

k,序列長為
n
,總塊數為
b=nk
,塊的編號從
0
開始,第
i
個元素所在的塊是
ik
,詢問有
q
筆。

要使用莫隊算法有一個先決條件:如果已經知道

[l,r] 的答案,那必須要可以快速地知道
[l,r+1]
[l,r1]
[l+1,r]
[l1,r]
的答案,也就是把左或右界移動一個位置,令算出新答案的複雜度為
O(P)
,有時候它可能是
O(logn)
,有時候會是
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
次左界(從一塊的開始移到下一塊的結尾),所以總次數大約是
2knk
,約等於
n
。然後左界在相同的塊時,右界會不斷往右移,因為我們剛剛是照右界位置排序,因此右界最多移動
n
次,總次數是
bn

左界在同一塊時,每次詢問左界最多移動

k 次,換塊的總移動次數是
n
,因此左界移動複雜度是
O(kq+n)
,而右界移動複雜度會是
O(bn)
,乘上算出新答案的複雜度
O(P)
再相加,就是
O((kq+n+bn)P)=O((kq+bn)P)

b 約為
nk
,根據算幾不等式,如果要讓
kq+bn
最小,那麼就要
kq=nkn
,解出來會得到
k=nq
,代回去後
kq+bn
會變成
nq
,複雜度變成
O(Pnq)
,如果
O(P)=O(1)
,那複雜度甚至只有
nq

帶修改

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

練習題