傳說中能解決一切區間處理問題的莫隊演算法是什麼？

12-29

參考這個https://zhuanlan.zhihu.com/p/25017840

這個演算法是用來處理一類無修改的離線區間詢問問題。

轉載自我的博客

問題：有n個數組成一個序列，有m個形如詢問L, R的詢問，每次詢問需要回答區間內至少出現2次的數有哪些。

　　樸素的解法需要讀取O(nm)次數。如果數據範圍小，可以用數組，時間複雜度為O(nm)。如果使用STL的Map來保存出現的次數，則需要O(nmlogn)的複雜度。有沒有更快的方法呢？

　　注意到詢問並沒有強制在線，因此我們可以使用離線方法。注意到一點，如果我們有計算完[L, R]時的「中間變數」（在本題為每個數出現的次數），那麼[L - 1, R]、[L + 1, R]、[L, R - 1]、[L, R + 1]都能夠在「中間變數」的「基本操作時間複雜度」(1)得出。如果能安排適當的詢問順序，使得每次詢問都能用上上次運行產生的中間變數，那麼我們將可以在更優的複雜度完成整個詢問。

(1) 如果數據較小，用數組，時間複雜度為O(1)；如果數據較大，可以考慮用離散化或map，時間複雜度為O(logn)。

　　那如何安排詢問呢？這裡有個時間複雜度非常優秀的方法：首先將每個詢問視為一個「點」，兩個點P1, P2之間的距離為abs(L1 - L2) + abs(R1 - R2)，即曼哈頓距離，然後求這些點的最小生成樹，然後沿著樹邊遍歷一次。由於這裡的距離是曼哈頓距離，所以這樣的生成樹被稱為「曼哈頓最小生成樹」。最小曼哈頓生成樹有專用的演算法(2)，求生成樹時間複雜度可以僅為O(mlogm)。

(2) 其實這裡是建邊的演算法，建邊後依然使用傳統的Prim或者Kruskal演算法來求最小生成樹。

　　不幸的是，曼哈頓最小生成樹的寫法很複雜，考場上不建議這樣做。　

　　一種直觀的辦法是按照左端點排序，再按照右端點排序。但是這樣的表現不好。特別是面對精心設計的數據，這樣方法表現得很差。

　　舉個例子，有6個詢問如下：(1, 100), (2, 2), (3, 99), (4, 4), (5, 102), (6, 7)。

　　這個數據已經按照左端點排序了。用上述方法處理時，左端點會移動6次，右端點會移動移動98+97+95+98+95=483次。右端點大幅度地來回移動，嚴重影響了時間複雜度——排序的複雜度是O(mlogm)，所有左端點移動次數僅為為O(n)，但右端點每個詢問移動O(n)，共有m個詢問，故總移動次數為O(nm)，移動總數為O(mlogm + nm)。運行時間上界並沒有減少。

　　其實我們稍微改變一下詢問處理的順序就能做得更好：(2, 2), (4, 4), (6, 7), (5, 102), (3, 99), (1, 100)。

　　左端點移動次數為2+2+1+2+2=9次，比原來稍多。右端點移動次數為2+3+95+3+1=104，右端點的移動次數大大降低了。

　　上面的過程啟發我們：①我們不應該嚴格按照升序排序，而是根據需要靈活一點的排序方法；②如果適當減少右端點移動次數，即使稍微增多一點左端點移動次數，在總的複雜度上看，也是划算的。

　　在排序時，我們並不是按照左右端點嚴格升序排序詢問，而只是令其左右端點處於「大概是升序」的狀態。具體的方法是，把所有的區間劃分為不同的塊，將每個詢問按照左端點的所在塊序號排序，左端點塊一樣則按照右端點排序。注意這個與上一個版本的不同之處在於「第一關鍵字」是左端點所在塊而非左端點。

　　這就是莫隊演算法。為什麼叫莫隊演算法呢？據說這是2010年國家集訓隊的莫濤 @莫濤 (3)在作業里提到了這個方法。

(3) 由於莫濤經常打比賽做隊長，大家都叫他莫隊，該演算法也被稱為莫隊演算法。（感謝汝佳大神、莫隊的指出）

　　莫隊演算法首先將整個序列分成√n個塊（同樣，只是概念上分的塊，實際上我們並不需要嚴格存儲塊），接著將每個詢問按照塊序號排序（一樣則按照右端點排序）。之後，我們從排序後第一個詢問開始，逐個計算答案。

int len; // 塊長度


struct Query{

    int L, R, ID, block;

    Query(){}　　// 構造函數重載

    Query(int l, int r, int ID):L(l), R(r), ID(ID){

        block = l / len;

    }

    bool operator &< (const Query rhs) const {
        if(block == rhs.block) return R &< rhs.R;　　// 不是if(L == rhs.L) return R &< rhs.R; return L &< rhs.L
        return block &< rhs.block;　　　　　　　　　　 // 否則這就變回演算法一了
    }
}queries[maxm];

map& buf;
inline void insert(int n){

    if(buf.count(n))

        ++buf[n];

    else

        buf[n] = 1;

}

inline void erase(int n){

    if(--buf[n] == 0) buf.erase(n);

}
int A[maxn];　　　　　　　　// 原序列

queue& anss[maxm];　　// 存儲答案

int main(){ int n, m; cin &>&> n; len = (int)sqrt(n);　　　　// 塊長度 for(int i = 1; i &<= n; i++){ cin &>&> A[i]; } cin &>&> m; for(int i = 1; i &<= m; i++){ int l, r; cin &>&> l &>&> r; queries[i] = Query(l, r, i); } sort(queries + 1, queries + m + 1); int L = 1, R = 1; buf[A[1]] = 1; for(int i = 1; i &<= m; i++){ queue& ans = anss[queries[i].ID]; Query qi = queries[i]; while(R &< qi.R) insert(A[++R]); while(L &> qi.L) insert(A[--L]); while(R &> qi.R) erase(A[R--]); while(L &< qi.L) erase(A[L++]); for(map&::iterator it = buf.begin(); it != buf.end(); ++it){ if(it-&>second &>= 2){ ans.push(it-&>first); } } } for(int i = 1; i &<= m; i++){ queue& ans = anss[i]; while(!ans.empty()){ cout &<&< ans.front() &<&< " "; ans.pop(); } cout &<&< endl; } }

　儘管分了塊，但是我們可以對所有的「詢問轉移」一視同仁。上述的代碼有幾個需要注意的地方。

　　一是insert和erase，這裡在插入前判斷了是否存在、插入後判斷是否為0，但這不是必須的（insert時會將新節點初始化為0，erase為0後對處理答案不影響）；

　　二是區間變化的順序，insert最好放在前面，erase最好在後面（想一想，為什麼）；

　　三是insert總是使用前綴自增自減運算符，erase總是用後綴運算符；

　　四是我們在訪問我們在「詢問轉移」前聲明了Query的引用，來減少運行時定址的計算量；

　　五是我們重載了Query的構造函數。為什麼要重載呢？

　　我們希望在Query得到L, R, ID時自動計算塊block，這就要寫一個構造函數Query(int L, int R, int ID)來實現。但是,當結構體沒有構造函數，實例化時不會初始化，有構造函數則一定會調用構造函數進行初始化。「托他的福」，queries數組建立時會對每個元素調用一次構造函數。可是我們只有有3個參數的構造函數，構造時一定要有3個參數。而建立數組時卻沒有參數，編譯器會報錯。折中的辦法是寫一個沒有參數的構造函數，可以避免這一問題。

　　這樣排序有個特點。L和R都是「大概是升序」。不過L大概像爬山，總體上升但是會有局部的小幅度下降。R則有些難以形容，大概可以看出其由很多段快速上升，每段上升到頂端後下降到最底。

　　下面是隨機生成100個數據，將數據放到WPS表格後製成圖表後的樣子。

　　還有一個問題，為什麼分塊要分成√n塊呢？我們分析一下時間複雜度。

　　假設我們每k個點分一塊。

　　如果當前詢問與上一詢問左端點處在同一塊，那麼左端點移動為O(k)。雖然右端點移動可能高達O(n)，但是整一塊詢問的右端點移動距離之和也是O(n)（想一想，為什麼）。因此平攤意義下，整塊移動為O(k) × O(k) + O(n)，一共有n / k塊，時間複雜度為O(kn + n2/ k)。

　　如果詢問與上一詢問左端點不處於同一塊，那麼左端點移動為O(k)，但右端點移動則高達O(n)。幸運的是，這種情況只有O(n / k)個，時間複雜度為O(n + n2

/ k)。總的移動次數為O(kn + n2 / k)。因此，當k = √n時，運行時間上界最優，為O( n1.5)。

　　最後，因此根據每次insert和erase的時間複雜度，乘上O(1)或者O(logn)亦或O(n)不等，得到完整演算法的時間複雜度（代碼使用了map，為O( logn )）。

　　十分感謝汝佳大神和莫隊對此文的指導orz。