本系列文章將于2021年整理出版，前驅教材：《演算法競賽入門到進階》清華大學出版社
網購：京東當當 ??作者簽名書：點我
有建議請加QQ 群：567554289

文章目錄

1. 基礎莫隊演算法

1.1 暴力法
1.2 區間查詢問題的幾何解釋
1.3 莫隊演算法
1.4 莫隊演算法的幾何解釋

2. 帶修改的莫隊
3. 樹上莫隊

（有讀者反映本文的公式顯示有問題，特別是和根號有關的公式，可能是網站的原因，請移步本文的博客園同步網址：https://www.cnblogs.com/luoyj/p/13643359.html
所有文章都在這里：https://www.cnblogs.com/luoyj/）

閱讀本文前，請先了解分塊演算法，參考我寫的博客：
https://blog.csdn.net/weixin_43914593/article/details/108474903

1. 基礎莫隊演算法

?? 莫隊演算法 = 離線 + 暴力 + 分塊，
??（莫隊：2010年資訊學國家集訓隊隊員莫濤，感謝莫濤對本文的圖6提出修改意見，）
?? “離線”和“在線”的概念，在線是互動式的，一問一答；如果前面的答案用于后面的提問，稱為“強制在線”，離線是非互動的，一次性讀取所有問題，然后一起回答，"記錄所有步，回頭再做”，
?? 基礎的莫隊演算法是一種離線演算法，它通常用于不修改只查詢的一類區間問題，復雜度 $O (n \sqrt{n}) O(n\sqrt{n})$ ，沒有在線演算法線段樹或樹狀陣列好，但是編碼很簡單，下面是一道莫隊模板題，

HH項鏈 洛谷 1972
題目描述：給定一個數量，詢問某個區間內不同的數有多少個，
輸入：第一行一個正整數 n，表示數列長度，第二行n個正整數 ai，第三行一個整數m，表示HH 詢問的個數，接下來 m 行，每行兩個整數 L,R，表示詢問的區間，
輸出：輸出m行，每行一個整數，依次表示詢問對應的答案，

??題目詢問區間內不同的數有多少個，即去重后數字的個數，本題的標準解法是線段樹或樹狀陣列，下面首先給出暴力法，然后再引匯出莫隊演算法，

1.1 暴力法

?? 可以用STL的unique()函式去重，一次耗時O(n)，m次的總復雜度O(mn)，或者自己編碼，用掃描法統計數字出現的次數，這是一種簡單易行的暴力法，
（1）查詢一個區間有多少個不同的數字
?? 定義cnt[]，cnt[x]表示數字x出現的次數；定義答案為ans，即區間內不同的x有多少個，
?? 用指標L、R單向掃描，從數列的頭掃到尾，L最終落在查詢區間的最左端，R落在區間最右端，L往右每掃一個數x，就把它出現的次數cnt[x]減去1；R往右每掃到一個數x，就把它出現的次數cnt[x]加上1，掃描完區間后，cnt[x]的值就是x在區間內出現的次數，若cnt[x]=1說明x第1次出現，ans加1；若cnt[x]變為0，說明它從區間里消失了，ans減1，
?? 下面的例子是統計區間[3, 7]內有多少不同的數字，初始指標L=1，R=0，

圖1 統計一個區間

??圖(1)：L=1、R=0時，cnt[4]=0, cnt[7]=0, cnt[9]=0…答案ans=0，
??圖(2)：L=2、R=0時，cnt[4]=-1, cnt[7]=0，
??圖(3)：L=3、R=2時，cnt[4]=0, cnt[7]=0, cnt[9]=0…
??圖(4)：L=3、R=3時，cnt[4]=0, cnt[7]=0, cnt[9]=1，出現了一個等于1的cnt[9]，答案ans = 1，
??圖(5)：L=3、R=7時，cnt[4]=1, cnt[7]=0, cnt[9]=1, cnt[6]=2, cnt[3]=1,…其中cnt[4], cnt[9], cnt[6], cnt[3]都出現過等于1的情況，所以答案ans = 4，
（2）統計多個區間
?? 從上面查詢一個區間的討論可以知道，在L、R移動程序中，當它們停留在區間[L, R]時，就得到了這個區間的答案ans，那么對m個詢問，只要不斷移動L、R并與每個詢問的區間匹配，就得到了m個區間詢問的答案，
?? 為了方便操作，可以把所有詢問的區間按左端點排序；如果左端點相同，再按右端點排序，討論以下情況：
?? 1）簡單情況，區間交錯，區間[x1, y1]、[x2, y2]的關系是x1 ≤ x2，y1 ≤ y2，例如下圖中，查詢兩個區間[2, 6]、[4, 8]，

圖2 簡單情況

??圖(1)L、R停留在第1個區間上，得到了第1個區間的統計結果；圖(2)L、R停留在第2個區間上，得到了第2個區間的結果，m次查詢的m個區間，L、R指標只需要從左頭到右（單向移動）掃描整個陣列一次即可，總復雜度O(n)，
?? 2）復雜情況，既有區間交錯，又有區間包含，區間[x1, y1]、[x2, y2]的包含關系是指x1 ≤ x2，y1 ≥ y2，例如下圖中，區間[2, 9]包含了區間[3, 5]，此時L從頭到尾單向掃描，而R指標卻需要來回往復掃描，每次掃描的復雜度是O(n)，m次查詢的總復雜度是O(mn)，

圖3 復雜情況

??R往復移動的時候，R往左每掃一個數x，就把它出現的次數cnt[x]減去1，

1.2 區間查詢問題的幾何解釋

??洛谷P1972的區間查詢問題，可以概況為這樣一種離線的幾何模型：
??（1）m個詢問對應m個區間，區間之間的轉移，可以用L、R指標掃描，能以O(1)的復雜度從區間[L,R]移動到[L±1, R±1]，
??（2）把一個區間[L, R]看成平面上的一個坐標點(x, y)，L對應x，R對應y，那么區間的轉移等同于平面上坐標點的轉移，計算量等于坐標點之間的曼哈頓距離，注意，所有的坐標點(x, y)都滿足x ≤ y，即所有的點都分布在上半平面上，
??（3）完成m個詢問，等于從原點出發，用直線連接這m個點，形成一條“Hamilton路徑”，路徑的長度就是計算量，若能找到一條最短的路徑，計算量就最少，
??Hamilton最短路徑問題是NP難度的，沒有多項式復雜度的解法，那么有沒有一種較優的演算法，能快速得到較好的結果呢？
??暴力法是按照坐標點(x, y)的x值排序而生成的一條路徑，它不是好演算法，例如下圖(1)的簡單情況，暴力法的順序是好的；但是圖(2)的復雜情況，暴力法的路徑是(0, 0)-(2, 9)-(3, 5)，曼哈頓距離(2-0) + (9-0) + (3-2) + (9-5) = 16，不如另一條路徑(0, 0)-(3, 5)-(2, 9)，曼哈頓距離 = 13，

圖4 暴力法的路徑

??下面介紹的莫隊演算法，提出了一種較好的排序方法，

1.3 莫隊演算法

??莫隊演算法把排序做了簡單的修改，就把暴力法的復雜度從O(mn)提高到 $O (n \sqrt{n}) O(n\sqrt{n})$ ，
??（1）暴力法的排序：把查詢的區間按左端點排序，如果左端點相同，再按右端點排序，
??（2）莫隊演算法的排序：把陣列分塊（分成 $\sqrt{n} \sqrt{n}$ 塊），然后把查詢的區間按左端點所在塊的序號排序，如果左端點的塊相同，再按右端點排序（注意不是按右端點所在的塊排序，下一小節“莫隊演算法的幾何解釋”將說明原因），
?? 除了排序不一樣，莫隊演算法和暴力法的其他步驟完全一樣，
?? 這個簡單的修改是否真能提高效率？下面分析多種情況下莫隊演算法的復雜度，
?? （1）簡單情況，區間交錯，設區間[ $P_{1}, y_{1} P_1, y_1$ ]、[ $P_{2}, y_{2} P_2, y_2$ ]的關系是 $P_{1} < P_{2} P_1 < P_2$ ， $y_{1} \leq y_{2} y_1 ≤ y_2$ ，其中 $P_{1} 、 P_{2} P_1、P_2$ 是左端點所在的塊，L、R只需要從左到右掃描一次，m次查詢的總復雜度是O(n)，
?? （2）復雜情況，區間包含，設兩個區間查詢[ $P_{1}, y_{1} P_1, y_1$ ]、[ $P_{2}, y_{3} P_2, y_3$ ]的關系是 $P_{1} = P_{2} ， y_{2} \leq y_{1} P_1 = P_2，y_2 ≤ y_1$ ，，如下圖所示，

圖5 按塊排序后的區間包含

??此時小區間[ $P_{2}, y_{2} P_2, y_2$ ]排在大區間[ $P_{1}, y_{1} P_1, y_1$ ]的前面，與暴力法正好相反，在區間內，右指標R從左到右單向移動，不再往復移動，而左指標L發生了回退移動，但是被限制在一個長為的塊內，每次移動的復雜度是O( $\sqrt{n} \sqrt{n}$ )的，m次查詢，每次查詢左端點只需要移動O( $\sqrt{n} \sqrt{n}$ )次，右端點R共單向移動O(n)次，總復雜度O(n $\sqrt{n} \sqrt{n}$ )，
?? （3）特殊情況：m個詢問，端點都在不同的塊上，此時莫隊演算法和暴力法是一樣的，但此時m小于，總復雜度O(mn) = O( $\sqrt{n} \sqrt{n}$ n)，

1.4 莫隊演算法的幾何解釋

?? 莫隊演算法的幾何意義見圖6(感謝莫濤對此圖提出修改意見)，這張圖透徹說明了莫隊演算法的原理，圖中的每個黑點是一個查詢，
??圖(1)是暴力法排序后的路徑，所有的點按x坐標排序，在復雜情況下，路徑沿y方向來回往復，震蕩幅度可能非常大（縱向震蕩，幅度 $O (n) O(n)$ ），導致路徑很長，
??圖(2)是莫隊演算法排序后的路徑，它把x軸分成多個區（分塊），每個區內的點按y坐標排序，在區內沿x方向來回往復，此時震蕩幅度被限制在區內（橫向震蕩，幅度 $O (\sqrt{n}) O(\sqrt{n})$ ），形成了一條比較短的路徑，從而實作了較好的復雜度，

圖6 暴力法和莫隊演算法的幾何對比

??通過圖(2)可以更清晰地計算莫隊演算法的復雜度：
??（1）x方向的復雜度，在一個區塊內，沿著x方向一次移動最多 $\sqrt{n} \sqrt{n}$ ，所有區塊共有m次移動，總復雜度 $O (m \sqrt{n}) O(m\sqrt{n})$ ，
??（2）y方向的復雜度，在每個區塊內，沿著y方向單向移動，整個區塊的y方向長度是n，有 $\sqrt{n} \sqrt{n}$ 個區塊，總復雜度 $O (n \sqrt{n}) O(n\sqrt{n})$ ，
??兩者相加，總復雜度 $O (m \sqrt{n} + n \sqrt{n}) O(m\sqrt{n}+n\sqrt{n})$ ，一般情況下題目會給出n = m，
??根據圖6總結出莫隊演算法的核心思想：把暴力法的y方向的O(n) 幅度的震蕩，改為x方向的受限于區間的O( $\sqrt{n} \sqrt{n}$ )幅度的震蕩，從而減少了路徑的長度，提高了效率，
??前面曾提到排序問題，對區間排序是先按左端點所在塊排序，再按右端點排序，不是按右端點所在的塊排序，原因解釋如下：如果右端點也按塊排序，幾何圖就需要畫成一個方格圖，方格中的點無法排序，實際的結果就是亂序，那么同一個方格內的點，在y方向上就不再是一直往上的復雜度為O(n)的單向移動，而是忽上忽下的往復移動，導致路徑更長，復雜度變差，見圖7所演示的路徑，

圖7 右端點按塊排序是錯誤的

??編碼時，還可以對排序做一個小優化：奇偶性排序，讓奇數塊和偶數塊的排序相反，例如左端點L都在奇數塊，則對R從大到小排序；若L在偶數塊，則對R從小到大排序（反過來也可以：奇數塊從小到大，偶數塊從大到小），
??這個小優化對照圖4.200(2)很容易理解，圖中路徑在兩個區塊之間移動時，是從左邊區塊的最大y值點移動到右邊區塊的最小y值點，跨度很大，用奇偶性排序后，奇數塊的點從最大y值到最小y值點排序，偶數塊從最小y值點到最大y值點排序；那么奇數塊最后遍歷的點是最小y值點，然后右移到偶數塊的最小y值點，這樣移動的距離是最小的，從偶數塊右移到奇數塊的情況類似，
??下面是洛谷P1972的代碼，莫隊演算法和暴力法唯一不同的地方在比較函式cmp()中，

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
struct node{         //離線記錄查詢操作
  int L, R, k;       //k：查詢操作的原始順序
}q[maxn];
int pos[maxn];
int ans[maxn];
int cnt[maxn];       //cnt[i]: 統計數字i出現了多少次
int a[maxn];
bool cmp(node a, node b){
	//按塊排序，就是莫隊演算法：
	if(pos[a.L] != pos[b.L])        //按L所在的塊排序，如果塊相等，再按R排序
		return pos[a.L] < pos[b.L];
	if(pos[a.L] & 1)   return a.R > b.R; //奇偶性優化，如果洗掉這一句，性能差一點
	return a.R < b.R;     
		/*如果不按塊排序，而是直接L、R排序，就是普通暴力法：
		if(a.L==b.L)  return a.R < b.R;
    	return a.L < b.L;   */
}
int ANS = 0;
void add(int x){     //擴大區間時（L左移或R右移），增加數x出現的次數
    cnt[a[x]]++;
    if(cnt[a[x]]==1)  ANS++;   //這個元素第1次出現
}
void del(int x){     //縮小區間時（L右移或R左移），減少數x出現的次數
    cnt[a[x]]--;
    if(cnt[a[x]]==0)  ANS--;   //這個元素消失了
}
int main(){	
    int n; scanf("%d",&n);
    int block = sqrt(n);         //每塊的大小
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);       //讀第i個元素
		pos[i]=(i-1)/block + 1;  //第i個元素所在的塊
    }
    int m; scanf("%d",&m);          
    for(int i=1;i<=m;i++){       //讀取所有m個查詢，離線處理
        scanf("%d%d",&q[i].L, &q[i].R);
        q[i].k = i;              //記錄查詢的原始順序
    }
    sort(q+1, q+1+m, cmp);       //對所有查詢排序
	int L=1, R=0;                //左右指標的初始值，思考為什么？
    for(int i=1;i<=m;i++){
       	while(L<q[i].L)  del(L++);    //{del(L); L++;}  //縮小區間：L右移
        while(R>q[i].R)  del(R--);    //{del(R); R--;}  //縮小區間：R左移
		while(L>q[i].L)  add(--L);    //{L--; add(L);}  //擴大區間：L左移
        while(R<q[i].R)  add(++R);    //{R++; add(R);}  //擴大區間：R右移
        ans[q[i].k] = ANS;
    }
    for(int i=1;i<=m;i++)   printf("%d\n",ans[i]);  //按原順序列印結果
    return 0;
}

2. 帶修改的莫隊

??上一節的基礎莫隊演算法只用于無修改只查詢的區間問題，如果是比較簡單的“單點修改”，也能應用莫隊演算法，得到復雜度 $O (m n^{\frac{2}{3}}) O(mn^{\frac{2}{3}})$ 的演算法，
??下面的例題是“單點修改 + 區間詢問”，

數顏色 洛谷P1903
題目描述：有n個數（其中有些數可能相同），擺成一排，有以下操作：
Q L R 詢問：從第L到第R個數，有幾個不同的數，
R P Col 修改：把第P個數改成Col，
輸入：第1行兩個整數n，m，分別代表初始數量以及操作個數，
第2行n個整數，分別代表初始數列中第i個數，
第3行到第2 + m行，每行分別一個操作，
輸出：對于每一個詢問，輸出一個數字，代表第L到第R個數共有幾個不同的數，

??如果用莫隊演算法求解，必須離線，先把查詢操作和修改操作分別記錄下來，記錄查詢操作的時候，增加一個變數，記錄本次查詢前做了多少次修改，
??如果沒有修改，就是基礎莫隊，一個查詢的左右端點是[L, R]，加上修改之后，一個查詢表示為(L, R, t)，t表示在查詢[L, R]前進行了t次修改操作，可以把t理解為“時間”，t的范圍是1 ≤ t ≤ m，m是操作次數，
??從一個查詢移動到另一個查詢，除了L、R發生變化外，還要考慮t的變化，如果兩個查詢的t相同，說明它們是基于同樣的數列；如果t不同，兩個查詢所對應的數列是不同的，那么就需要補上這變化（直接用暴力法編程），兩個查詢的t相差越小，它們對應的數列差別越小，計算量也越小，所以對t排序能減少計算量，
??與基礎莫隊一樣，也可以給出帶修改莫隊的幾何解釋，基礎莫隊的左右端點[L, R]，對應平面上的點( $x, y x, y$ ) ，帶修改的莫隊(L, R, t)對應立體空間的( $x, y, z x, y, z$ )，每個查詢對應立體空間的一個點，那么從一個查詢到另一個查詢，就是從一個點( $x_{1}, y_{1}, z_{1} x_1, y_1, z_1$ )到另一個點( $x_{2}, y_{2}, z_{2} x_2, y_2, z_2$ )，計算復雜度仍然是兩點之間的曼哈頓距離，
??模仿基礎莫隊的分塊思路，定義帶修改莫隊的排序，按以下步驟執行：
?? （1）按左端點L排序，若左端點L在同一個塊，執行（2），L對應 $x x$ 軸，
?? （2）按右端點R排序，若右端點R在同一個塊，執行（3），R對應 $y y$ 軸，
?? （3）按時間t排序，t對應 $z z$ 軸，
?? 左端點L所在的塊是第1查詢關鍵字，右端點R所在的塊是第2關鍵字，時間t是第3關鍵字，
?? x方向和y方向的分塊，把 $x x$ - $y y$ 平面分成了方格，代表查詢的點在方格內、方格間移動，
?? 根據帶修改莫隊的幾何意義，計算演算法的復雜度，這里先不采用的分塊方法，而是設一個分塊的大小是B，共有n/B個分塊，計算 $x 、 y 、 z x、y、z$ 三個方向上的復雜度：
??（1） $x x$ 方向的復雜度（左端點指標L），在一個區塊內，沿著 $x x$ 方向一次最多移動B，所有的區塊共有m次移動，總計算量 = $m B mB$ ，
??（2） $y y$ 方向的復雜度（右端點指標R），在一個區塊內，沿著 $y y$ 方向一次最多移動B，所有的區塊共有m次移動，總計算量 = $m B mB$ ，
??（3） $z z$ 方向的復雜度（時間t），每個被 $x x$ 和 $y y$ 區塊限制的方格內，沿著 $z z$ 方向單向移動，最多移動m次，共 $\frac{n^{2}}{B^{2}} \frac{n^2}{B^2}$ 個方格，總計算量 = $\frac{m n^{2}}{B^{2}} \frac{mn^2}{B^2}$ ，
??三者相加，總計算量 = $m B + m B + \frac{m n^{2}}{B^{2}} mB+mB+\frac{mn^2}{B^2}$ ，當 $B = n^{\frac{2}{3}} B = n^\frac{2}{3}$ 時有較好的復雜度 $O (m n^{\frac{2}{3}}) O(mn^{\frac{2}{3}})$ ，
??作為對照，如果分塊 $B = \sqrt{n} B = \sqrt{n}$ ，復雜度是 $O (m n) O(mn)$ ，退化成了暴力法的復雜度，

3. 樹上莫隊

??基礎莫隊和帶修改的莫隊操作的都是一維陣列，基于其他的資料結構的問題，如果能轉換成一維陣列而且是區間問題，那么也能應用莫隊演算法，
??典型的例子是樹形結構上的路徑問題，可以利用“歐拉序”把整棵樹的結點順序轉化為一個一維陣列，路徑問題也變成了區間問題，就能利用莫隊演算法求解，下面的簡單題體現了這個思路，

Count on a tree II 洛谷 SP10707
題目描述：給定有n個結點的數，每個結點有一種顏色，m次詢問，每次詢問給出兩個結點u、v，回答從u到v的路徑上有多少個不同顏色的結點，
輸入：第一行是n和m，第二行有n個整數，第i個整數表示第i個結點的顏色，下面n-1行，每行有兩個整數u、v，表示一個邊(u, v)，下面m行，每行有兩個整數u、v，表示一個詢問，回答從結點u到v的路徑上有多少個不同顏色的結點，
輸出：對每個詢問，輸出一個整數，
資料范圍：1 ≤ n ≤ 4× $1 0^{4} 10^4$ ，1 ≤ m ≤ $1 0^{5} 10^5$

思路：
1、把樹的結點用歐拉序轉為一維陣列
??用DFS遍歷樹的結點，有兩種遍歷方式，得到兩種歐拉序：
??（1）在每個結點第一次進和最后一次出都加進序列；
??（2）每遇到一個結點就把它加進序列，
??這里用第（1）種形式的歐拉序，下圖的例子，歐拉序：{1, 2, 2, 3, 5, 5, 6, 6, 7, 7, 3, 4, 8, 8, 4, 1}，

圖8 一棵樹

??(u, v)上的路徑有哪些結點？首先計算出u、v的lca(u, v)（最近公共祖先），然后討論兩種情況：
??（1）lca(u, v) = u或lca(u, v) = v，即u在v的子樹中，或者v在u的子樹中，例如u = 1, v = 6，區間是{1, 2, 2, 3, 5, 5, 6}，出現2次的結點{2, 5}不屬于這條路徑，因為它進來了又出去了，只出現一次的結點屬于這條路徑，即{1, 3, 6}，
??（2）lca(u, v) ≠ u且lca(u, v) ≠ v，即u和v都不在對方的子樹上，此時u、v之間的路徑需要通過它們的lca，但是lca沒有出現在u和v的歐拉序區間內，需要添上，例如u = 5，v = 8，區間是{5, 6, 6, 7, 7, 3, 4, 8}，去掉出現2次的結點{6, 7}，剩下{5, 3, 4, 8}，再加上它們的lca = 1，得路徑{5, 3, 4, 8, 1}，再例如u = 5，v = 7，區間是{5, 6, 6, 7}，去掉6，剩下{5, 7}，再加上它們的lca = 3，得路徑{5, 7, 3}，
2、本題的求解步驟
??（1）求樹的歐拉序，得到一維陣列；求任意兩個點的lca，編碼時用樹鏈剖分（做兩次DFS）求歐拉序和lca，
??（2）把題目的查詢(u, v)看成一維陣列上的查詢，題目要求查詢(u, v)內不同的顏色，首先查區間(u, v)內只出現1次的結點，并加上u、v的lca，得到路徑上的所有結點，然后在這些結點中統計只出現1次的數字，
??（3）用莫隊演算法，離線處理所有的查詢，然后一起輸出，注意分塊時，本題的規模是2n，因為每個結點在歐拉序中出現2次；另外每個結點的顏色數值很大，需要離散化，

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/4740.html

標籤：python

上一篇：作業系統復習題

下一篇：L1-042 日期格式化 (5分)

莫隊演算法 --演算法競賽專題決議（26）