原發表于我的博客

前言

本來想學完回滾莫隊、樹上莫隊、二離莫隊之后一起寫一個博客，但是一直學不會/kk，只好把已會的普通莫隊和帶修莫隊寫了（以后會補上的）

普通莫隊

莫隊——優雅的暴力

莫隊算法的引入

例題：

給定一個數列和若干詢問，每次詢問詢問一段區間內不同種類數字的個數。

暴力做法

每次詢問暴力枚舉區間\([l,r]\)，用一個數組\(cnt\)記錄每個數在區間內出現的次數，最后枚舉\(cnt\)數組，記錄所有不為空的數的個數。

時間復雜度大概是\(O(q(n^2+m))\)，其中\(m\)為數據范圍，一定會TLE的。

改進做法1（依然暴力）

考慮到優化，在記錄每次枚舉區間的時候，記錄下不同數的個數，就剩下了最后枚舉數據范圍的步驟，時間復雜度變成\(O(n^2q)\)

但是依然會TLE

改進做法2（離線力）

考慮離線，把所有操作都讀入。

從第一個查詢操作開始，每次以\(O(1)\)的時間復雜度拓展。

如第一個查詢操作為\([l,r]\)，第二個操作查詢\([l-3,r+4]\)，那我們就一步一步地把\(l\)，向左移動，每次移動的時候把拓展的數字加入cnt，更新答案，\(r\)同理。

形象的理解就是維護兩個指針\(l,r\)，每次\(l,r\)左右移動的同時更新答案。

但是這種做法本質上還是\(O(n^2q)\)的（常數會小很多），所以我們需要繼續優化。

改進做法3（排序大法好）

上一個做法的低效之處在于，如果第一個操作數列后面，第二個操作在最前面，\(l\)指針就會從末尾一路走到最前面（漂洋過海來看你？），如果出題人這樣構造數據的話，復雜度就和最開始的暴力沒有區別了。

考慮到排序，按照\(l\)排序，讓\(r\)亂蹦跶，兩個指針有序地向后竄，時間復雜度就會變成\(O(qn \log n)\)

依然會TLE

改進做法4（莫隊算法！！！）

通過逐步的優化，我們已經摸索出了真正的莫隊算法！！！

莫隊算法其實就是通過某種神奇優化，把復雜度降低（莫隊orz），這種排序方法就很神奇（我也不會證）

考慮分塊,把數列分成\(\sqrt{n}\)塊。

優化上一個做法，排序時，第一個關鍵字為左端點所在塊編號，第二個關鍵字是右端點編號。

這種排序方式會把算法優化到\(O(n\sqrt{n})\)（沒法再優化了！！！）

具體證明我也不會，可以看link

那么代碼我們也能寫出來了。

代碼

const int N=1e6+10;
int cnt[N],a[N],ans=0;
struct node{
	int l,r,id,ans;
}que[N];
int T;
int Ans[N];
bool cmp(node a,node b){
	if(a.l/T==b.l/T) return a.r<b.r;//第二個關鍵字按照右端點編號排序
	return a.l/T<b.l/T;//第一個關鍵字按照左端點所在塊編號排序
}
void add(int x){
	//拓展一個數
	if(!cnt[x]) ans++;//若這個數還沒有過，更新答案
	cnt[x]++;
}
void del(int x){
	cnt[x]--;
	if(!cnt[x]) ans--;
}
int n,m;
int main(){
	cin>>n;
	T=sqrt(n);//分塊
	for(int i=1;i<=n;i++) cin>>a[i];
	cin>>m;
	for(int i=1;i<=m;i++) cin>>que[i].l>>que[i].r,que[i].id=i;
	sort(que+1,que+1+m,cmp);//排序
	int l=1,r=0;//最開始的lr指針應該是個空區間
	for(int i=1;i<=m;i++){
		//分別拓展
		while(r<que[i].r) add(a[++r]);
		while(r>que[i].r) del(a[r--]);
		while(l>que[i].l) add(a[--l]);
		while(l<que[i].l) del(a[l++]);
		Ans[que[i].id]=ans;//記錄答案
	}
	for(int i=1;i<=m;i++) cout<<Ans[i]<<endl;
}

這個代碼其實就是洛谷P1972 HH的項鏈，但由于某洛谷知名管理員加強了數據，這題莫隊就過不去了（親測莫隊能卡到48，聽說有人卡到了92）。

奇偶性優化

如果\(l\)在奇數塊，就按照\(r\)順序排序，否則按照\(r\)逆序排序。

inline bool cmp(Que a,Que b){
	if(a.l/T!=b.l/T) return a.l/T<b.l/T;
	if((a.l/T)&1) return a.r<b.r;
	return a.r>b.r;
}

這個優化很有用，但是一般只會在卡常的時候用到。

例題1：小B的詢問

原題

解題思路

在HH的項鏈被卡了后，這題就算是莫隊模板了。

思路：用一個\(cnt\)數組維護區間內數字個數，然后加減時答案增刪平方，剩下就是普通莫隊了。

AC代碼

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int cnt[N],a[N],ans=0;
struct Que{
	int l,r,id;//查詢結構題
}que[N];
int T,Ans[N];
bool cmp(Que a,Que b){
	if(a.l/T!=b.l/T) return a.l/T<b.l/T;//第一個關鍵字為左端點所在塊編號
	return a.r<b.r;//第二個關鍵字為右端點編號
}
void add(int x){
	ans-=cnt[x]*cnt[x];
	cnt[x]++;
	ans+=cnt[x]*cnt[x];
}
void del(int x){
	ans-=cnt[x]*cnt[x];
	cnt[x]--;
	ans+=cnt[x]*cnt[x];
}
int n,m,k;
int main(){
	cin>>n>>m>>k;
	T=sqrt(n);
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>que[i].l>>que[i].r,que[i].id=i;//離線讀入詢問
	sort(que+1,que+1+m,cmp);//先排序
	int l=1,r=0;//起始lr指針設為一個空區間
	for(int i=1;i<=m;i++){
		//莫隊算法
		while(r<que[i].r) add(a[++r]);
		while(r>que[i].r) del(a[r--]);
		while(l>que[i].l) add(a[--l]);
		while(l<que[i].l) del(a[l++]);
		Ans[que[i].id]=ans;//記錄答案
	}
	for(int i=1;i<=m;i++) cout<<Ans[i]<<endl;
}

帶修莫隊

帶修改的莫隊就是在莫隊的基礎上多了一個修改操作（廢話）

如果說普通的莫隊是從\([l_1,r_1]\)轉移到\([l_2,r_2]\)，那帶修改的莫隊就是從\([l_1,r_1,t_1]\)轉移到\([l_2,r_2,t_2]\)。

所以我們可以把修改操作也存下來，執行莫隊算法的時候，先按照普通莫隊的做法轉移到下一個區間，然后再進行（或撤銷）這兩次查詢之間進行的修改，就相當于轉移到了目標的詢問。

可以把帶修莫隊理解成一個多了時間的坐標軸，如圖

至于實現，則比較簡單，排序時以左端點所在塊編號為第一個關鍵字，右端點所在塊編號為第二個關鍵字，第三個關鍵字是時間戳（在這次查詢前右多少次修改）。

普通莫隊維護兩個指針\(l,r\)，帶修莫隊多維護一個指針\(t\)即可。

另外分塊時不能以\(\sqrt{n}\)分了，帶修莫隊一般一塊\(n^{\frac{2}{3}}\)，分成\(n^{\frac{1}{3}}\)塊，復雜度為\(O(n^{\frac{3}{5}})\)（不會證明，可以看oiwiki）

例題2：數顏色

原題

帶修莫隊模板題。

AC代碼

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int T;
struct Que{
	int l,r,id,tim;
}que[N];
int as[N];
bool cmp(Que a,Que b){
	if(a.l/T==b.l/T){
		if(a.r/T==b.r/T) return a.tim<b.tim;
		return a.r/T<b.r/T;
	}
	return a.l/T<b.l/T;
}
struct Upd{
	int p,col;
}upd[N];
int cnt[N],ans=0,a[N];
void add(int x){
	if(!cnt[x]) ans++;
	cnt[x]++;
}
void del(int x){
	cnt[x]--;
	if(!cnt[x]) ans--;
}
int n,m,iq=0,ic=0;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++){
		char opt;
		int l,r;
		cin>>opt>>l>>r;
		if(opt=='Q') que[++iq]={l,r,iq,ic};
		else upd[++ic]={l,r};
	}
	T=pow(n,0.666);//即n^2/3
	sort(que+1,que+1+iq,cmp);//排序
	int l=1,r=0,now=0;//三個指針
	for(int i=1;i<=m;i++){
		//這部分和普通莫隊差不多
		while(l<que[i].l) del(a[l++]);
		while(l>que[i].l) add(a[--l]);
		while(r>que[i].r) del(a[r--]);
		while(r<que[i].r) add(a[++r]);
		//轉移到新詢問的時間戳
		while(now<que[i].tim){
			++now;
			int p=upd[now].p,c=upd[now].col;
			if(l<=p&&p<=r) del(a[p]),add(c);
			swap(a[p],upd[now].col);
		}
		while(now>que[i].tim){
			int p=upd[now].p,c=upd[now].col;
			if(l<=p&&p<=r)	del(a[p]),add(c);
			swap(a[p],upd[now].col);
			now--;
		}
		as[que[i].id]=ans;//記錄答案
	}
	for(int i=1;i<=iq;i++) cout<<as[i]<<endl;
}