聽說莫隊算法是一種“優雅的暴力”（小聲bb）。

普通莫隊

1/ 引入

problem：給你一個長度為n的數組，有m次查詢，每次查詢詢問一個區間[L, R]内有多少個不同的數。

首先想想暴力怎麼做。

開一個數組用來記數，然後掃一遍[L,R]，如果這個數是第一次出現，那麼對答案貢獻+1。暴力出來的時間複雜度是O(n*m)，如果n、m較大，那暴力肯定是不行的。
再想想進一步優化。

開兩個指針 l 和 r，将之前的每次掃區間[L,R]改成移動指針l、r，使得指針與區間邊界對齊。在移動指針的時候，對應地去删除或添加對答案的貢獻即可。但問題來了，如果每次詢問的區間[L,R]都需要移動很長的距離，就比如第一次詢問[1,2]，第二次詢問[n-1,n]，這麼一來時間複雜度依舊是O(n*m)。優化了個寂寞

2/ 莫隊算法的實作

回到剛才的第二種思路，我們可不可以在原來的基礎上，對左區間進行排序以保證指針l不會移動到曾經被左指針掃過的地方，思想是好的，但是不能確定指針r的移動不重複，是以還是不行。

這個時候就需要莫隊算法了。它的核心是分塊和排序：将長度為n的數組分為若幹個塊，每個塊内有sqrt(n)個元素，再将每個塊按順序編号，然後排序（對于區間左端點來說，如果在同一個塊内，就按右端點排序，否則按左端點排序）。時間複雜度是O(n^1.5)，優化了很大一部分。詳細的時間複雜度證明可自行百度

另外多數莫隊題的輸入輸出量是比較大的，用cin大機率會tle，老老實實用scanf或者快讀吧。

如果足夠細心應該會注意到，對要詢問的區間進行排序，那将會打亂原有的詢問順序。換而言之，必須要先輸入所有詢問，再一次性輸出所有對應的答案，也就是我們通常所說的離線操作

Code

資料說明：

e[ ].l ：詢問的左端點。 e[ ].r ：詢問的右端點。 e[ ].id ：詢問的次序。
size ：每個區間的大小，即 sqrt(n)。
cnt[i] ：記 i 出現的次數。
belong[i] ：記 i 屬于的塊的編号，即 i/size。

結構體排序（未優化）：

bool cmp(node x, node y) {
	if (belong[x.l] == belong[y.l]) return x.r < y.r;
	return x.l < y.l;
}

.結構體排序（優化後）：

bool cmp(node x, node y) {
	return belong[x.l]^belong[y.l] ? x.l < y.l : (belong[x.l]&1)? x.r < y.r : x.r > y.r;
}

首先用位運算代替了if，這樣會快些。另外對于左端點在同一奇數塊的區間，右端點按升序排列，反之降序（不論奇數升序偶數降序、還是偶數升序奇數降序其實都是不影響優化後的複雜度的），時間大概能優化一半吧，至于奇偶排序具體原理嘛。。。簡單來說， emm還是畫個圖吧（靈魂畫手show time）

莫隊（普通莫隊，帶修莫隊，樹上莫隊）普通莫隊帶修莫隊樹上莫隊
這裡R指針的移動是上下上下上，這是按照R升序排列的，那按照奇偶排列的話，那就是這樣的：

莫隊（普通莫隊，帶修莫隊，樹上莫隊）普通莫隊帶修莫隊樹上莫隊
R指針隻需要上下上就完成了，就相當于把兩個波峰合并成了一個波峰，那麼掃過的路徑就會減少大緻一半，進而優化了近一半的時間。

完整代碼：

const int maxn = 1e6+5;

struct node {
	int l, r, id;
}e[maxn];
int n, m, size, l, r;
ll a[maxn], ans[maxn], cnt[maxn], sum;
int belong[maxn];

// 優化 
bool cmp(node x, node y) {
	return belong[x.l]^belong[y.l] ? x.l < y.l : (belong[x.l]&1)? x.r < y.r : x.r > y.r;
}
/* 
bool cmp(node x, node y) {
	if (belong[x.l] == belong[y.l]) return x.r < y.r;
	return x.l < y.l;
}
*/ 

void add(int pos) {
	if (!cnt[a[pos]]) sum++;
	cnt[a[pos]]++;
}
void del(int pos) {
	cnt[a[pos]]--;
	if (!cnt[a[pos]]) sum--;
}
int main() {
	read(n);
	size = sqrt(n);
	for (int i = 1; i <= n; i++) {
		read(a[i]);
		belong[i] = (i-1)/size;
	} 
	read(m);
	for (int i = 1; i <= m; i++) {
		read(e[i].l), read(e[i].r);
		e[i].id = i;
	}
	sort(e+1, e+1+m, cmp);
	l = 1, r = 0, sum = 0;
	for (int i = 1; i <= m; i++) {
		while (l < e[i].l) del(l++);
		while (l > e[i].l) add(--l);
		while (r < e[i].r) add(++r);
		while (r > e[i].r) del(r--);
		ans[e[i].id] = sum;
	}
	for (int i = 1; i <= m; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}

帶修莫隊

1/ 引入

前面說過莫隊算法是離線算法，按理來說，輸入的資料是不能修改的，但是對于一些允許離線的需要修改區間的查詢來說，帶修莫隊也是可以解決的。

2/ 帶修莫隊的實作

其實和普通莫隊差不多，之前不是用到了指針L，R嘛，帶修莫隊的差別就在于加了一個次元------時間。

如果不修改的話，就沿用之前的時間戳；修改的話時間戳++，并記錄修改的資訊。進行查詢操作時，通過移動time、L和R指針，使得目前區間與所查詢區間的左右端點、時間戳均相同，所得即答案。

說白了就是在之前[l,r+1]、[l,r-1]、[l+1,r]、[l-1,r] （時間戳不變）的基礎上，再加兩個[l,r,t+1]、[l,r,t-1]就行了。

至于排序嘛，升序排列，優先級是L，R，time。

當修改後，有可能要改回來，是以還要記錄好原來的值。但其實也可以不存，隻要在修改後把修改的值和原值交換一下，那麼改回來時也隻要交換一下，兩次交換後不就相當于還原了嘛。

還有一點就是關于塊的大小，經過證明，當塊的大小為(n^4*t)的立方根時複雜度最優。塊的大小可以取pow(n,2.0/3.0)，那麼時間複雜度為pow(n,5.0/3.0) 。這個時間還能接受吧。

Code

const int maxn = 2e6+5;
int n, m, siz, cntq, cntc, now, t, l, r;
int a[maxn], belong[maxn], ans[maxn], cnt[maxn]; 

struct node1 {
	int l, r, id, tim;
}e[maxn];
struct node2 {
	int pos, val;
}c[maxn];

bool cmp(node1 x, node1 y) {
	return (belong[x.l]^belong[y.l]) ? x.l<y.l : (belong[x.r]^belong[y.r]) ? x.r < y.r : x.tim < y.tim;
}

void add(int x) {
	if (!cnt[a[x]]) now++;
	cnt[a[x]]++;
}
void del(int x) {
	cnt[a[x]]--;
	if (!cnt[a[x]]) now--;
}

int main() {
	read(n), read(m);
	siz = pow(n, 2.0/3);
	for (int i = 1; i <= n; i++) {
		read(a[i]);
		belong[i] = (i-1)/siz;
	}
	cntq = cntc = now = 0;
	for (int i = 1; i <= m; i++) {
		char op[50];
		scanf("%s", op);
		if (op[0] == 'Q') {
			read(e[++cntq].l);
			read(e[cntq].r);
			e[cntq].id = cntq;
			e[cntq].tim = cntc;
		} else {
			read(c[++cntc].pos);
			read(c[cntc].val);
		}
	}
	sort(e+1, e+1+cntq, cmp);
	
	l = 1, r = 0, t = 0;
	for (int i = 1; i <= cntq; i++) {
		while (l < e[i].l) del(l++);
		while (l > e[i].l) add(--l);
		while (r < e[i].r) add(++r);
		while (r > e[i].r) del(r--);
		while (t < e[i].tim) {
			t++;
			if (e[i].l <= c[t].pos && c[t].pos <= e[i].r) {
				del(c[t].pos);
				if (!cnt[c[t].val]) now++;
				cnt[c[t].val]++;
			}
			swap(a[c[t].pos], c[t].val);
		}
		while (t > e[i].tim) {
			if (e[i].l <= c[t].pos && c[t].pos <= e[i].r) {
				del(c[t].pos);
				if (!cnt[c[t].val]) now++;
				cnt[c[t].val]++;				
			}
			swap(a[c[t].pos], c[t].val);
			t--;
		}
		ans[e[i].id] = now;
	}
	for (int i = 1; i <= cntq; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}

樹上莫隊

1/ 引入

适用通常是：給你一棵樹，求點u到v之間有多少個不同的數。

2/ 樹上莫隊的實作

首先介紹歐拉序

莫隊（普通莫隊，帶修莫隊，樹上莫隊）普通莫隊帶修莫隊樹上莫隊

對于這棵樹，對應的歐拉序是：1 2 4 7 7 4 5 5 2 3 6 8 9 9 10 10 11 11 8 6 3 1

對照一下圖和序列，應該不難知道歐拉序的定義。

經過仔細的觀察，不難發現（直接上結論吧還是）

樹的歐拉序上兩個相同編号（設為x）之間的所有編号都出現兩次，且都位于x子樹上

（先假設你會求LCA，具體怎麼求後面會講）

那麼假設設每個點（編号為a）首次出現的位置first[a]，最後出現的位置為last[a]，那麼對于路徑u→v，不妨預設first[u]<=first[v]（不滿足的話交換就好了，這個操作的意義在于，如果u、v在一條鍊上，則u一定是v的祖先或等于v），相當于免去了分類讨論嘛。如果lca(u,v)=u，則直接查詢[first[u],first[v]]；否則查詢[last[u],first[v]]區間，但這個區間是不包含u和v的LCA的，隻需要在查詢的時候額外加上即可，這樣一來就把樹上的問題轉換成了區間問題，接下來就成了普通莫隊啦。

Code

const int maxn = 1e5+5;
int n, m, id, cntn, now;
int a[maxn], head[maxn], val[maxn], tmp[maxn], fir[maxn], las[maxn], ord[maxn], vis[maxn], f[maxn][30], dep[maxn], belong[maxn], cnt[maxn], ans[maxn];
// ord[]---歐拉序

struct node {
	int to, nex;
}e[maxn];
void addedge(int u, int v) { 
	e[++id].to = v;
	e[id].nex = head[u];
	head[u] = id;
}

void dfs(int x) {
	ord[++cntn] = x;
	fir[x] = cntn;
	for (int i = head[x]; i != -1; i = e[i].nex) {
		int to = e[i].to;
		if (to != f[x][0]) {
			dep[to] = dep[x] + 1;
			f[to][0] = x;
			for (int j = 1; (1 << j) <= dep[to]; j++) 
				f[to][j] = f[f[to][j-1]][j-1];
			dfs(to);
		}
	}
	ord[++cntn] = x;
	las[x] = cntn;
}

int LCA(int u, int v) { // LCA後面會有講解
	if (dep[u] < dep[v]) swap(u, v);
	for (int i = 20; i >= 0; i--)
		if (dep[f[u][i]] >= dep[v])
			u = f[u][i];
	if (u == v) return u;
	for (int i = 20; i >= 0; i--) {
		if (f[u][i] != f[v][i]) {
			u = f[u][i];
			v = f[v][i];
		}
	}
	return f[u][0];
}

struct node2 {
	int l, r, id, lca;
}q[maxn];
int cmp(node2 x, node2 y) {
	return (belong[x.l]^belong[y.l]) ? x.l < y.l : (belong[x.l]&1) ? x.r < y.r : x.r > y.r;  
}

void work(int pos) { //通過忽略走過兩遍的點（歐拉序的特性）
	vis[pos] ? now -= !(--cnt[val[pos]]) : now += !(cnt[val[pos]]++);
	vis[pos] ^= 1;
}

int main() {
	read(n), read(m);
	mem(head, -1);
	for (int i = 1; i <= n; i++) read(val[i]), tmp[i] = val[i];
	sort(tmp+1, tmp+1+n);
	// 資料範圍大，需要離散化
	int tot = unique(tmp+1, tmp+1+n) - tmp-1;
	for (int i = 1; i <= n; i++) {
		val[i] = lower_bound(tmp+1, tmp+tot+1, val[i]) - tmp;
	}
	for (int k = 1; k < n; k++) {
		int u, v;
		read(u), read(v);
		addedge(u, v);
		addedge(v, u);
	}
	dep[1] = 1;
	dfs(1);
	int siz = sqrt(cntn);
	for (int i = 1; i <= cntn; i++) {
		belong[i] = (i-1)/siz;
	}
	for (int i = 1; i <= m; i++) {
		int l, r, lca;
		read(l);
		read(r);
		lca = LCA(l, r);
		if (fir[l] > fir[r]) swap(l, r);
		if (l == lca) {
			q[i].l = fir[l];
			q[i].r = fir[r];
		} else {
			q[i].l = las[l];
			q[i].r = fir[r];
			q[i].lca = lca;
		}
		q[i].id = i;
	}
	sort(q+1, q+1+m, cmp);
	int l = 1, r = 0;
	for (int i = 1; i <= m; i++) {
		int ql = q[i].l, qr = q[i].r, qlca = q[i].lca;
		while (l < ql) work(ord[l++]);
		while (l > ql) work(ord[--l]);
		while (r < qr) work(ord[++r]);
		while (r > qr) work(ord[r--]);
		if (qlca) work(qlca); //lca不在序列内
		ans[q[i].id] = now;
		if (qlca) work(qlca); //還原
	}
	for (int i = 1;i <= m; i++) {
		cout << ans[i] << endl;
	}
	
	return 0;
}

莫隊（普通莫隊，帶修莫隊，樹上莫隊）普通莫隊帶修莫隊樹上莫隊

普通莫隊

1/ 引入

2/ 莫隊算法的實作

Code

帶修莫隊

1/ 引入

2/ 帶修莫隊的實作

Code

樹上莫隊

1/ 引入

2/ 樹上莫隊的實作

Code

繼續閱讀

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

【資料結構】醫院選址

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

[轉]ISUP信令的IAM消息詳細内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

hdu7108哈希