Competitive Programming Note
108 師大附中校隊培訓
本文已停止更新,新版請至 WiwiHo 的競程筆記
莫隊算法是一種用來處理區間問題的離線算法,也就是說,它會在把所有詢問讀進來之後,再利用詢問之間的關聯性來降低運算時間,所以它在像是 IOI 這種一定要先回傳答案才可以讀下一筆詢問的比賽不能用,但大多數的比賽都可以。
莫隊算法需要用到分塊法,令一塊大小為 ,序列長為 ,總塊數為 ,塊的編號從 開始,第 個元素所在的塊是 ,詢問有 筆。
要使用莫隊算法有一個先決條件:如果已經知道 的答案,那必須要可以快速地知道 、、、 的答案,也就是把左或右界移動一個位置,令算出新答案的複雜度為 ,有時候它可能是 ,有時候會是 ,視題目要你算什麼而定,至於算不算快就自己評估。
接下來是莫隊算法的過程,首先,讀入每一筆詢問,然後對每一筆詢問依左界所在的塊由小到大排序,相同的話依右界位置(非塊編號)由小到大排序,接著算出第一筆詢問的答案後,用移動邊界的方式來算出下一筆詢問的答案。
pseudo code:
只要把詢問的順序記下來,得出全部詢問的答案後依序輸出就好了。
再來是最重要的複雜度,乍看之下會覺得這樣一直加減加減的,一次還只移動一格,會不會太慢啊?
移動一次邊界算新答案是 ,然後左界在相同的塊中,每次詢問最多會移動 ,因為已經按照左界所在的塊排序了,排序後連續的幾個詢問左界會在同一個塊中,而換塊的話,往右換一塊最多就移動大約 次左界(從一塊的開始移到下一塊的結尾),所以總次數大約是 ,約等於 。然後左界在相同的塊時,右界會不斷往右移,因為我們剛剛是照右界位置排序,因此右界最多移動 次,總次數是 。
左界在同一塊時,每次詢問左界最多移動 次,換塊的總移動次數是 ,因此左界移動複雜度是 ,而右界移動複雜度會是 ,乘上算出新答案的複雜度 再相加,就是 。
約為 ,根據算幾不等式,如果要讓 最小,那麼就要 ,解出來會得到 ,代回去後 會變成 ,複雜度變成 ,如果 ,那複雜度甚至只有 。
莫隊算法除了做查詢,也可以做修改。但是我還在學。