首先來看一道例題：

Description
有n個數字，以及m個查詢。每次查詢的格式是L，r，求L~r（左右包含）這個區間內有多少個不同的數？
1< n，m<=50000，1<=L<r<=n，數列中元素大小<=n 。

思路1：

自然而然想到暴力，對每次詢問L~r枚舉區間，如果數列中元素取值范圍很大，先要進行離散化處理。
時間復雜度：O(nm)
代碼略

思路2：

線段樹或樹狀數組處理一下。（代碼復雜度相對而言較高）。

#include<cstdio>
#include<algorithm>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
int n,m;
int b[500010],c[500010],last[1000010],ans[500010];
struct node{int x,y,id;} a[500010];
bool cmp(node x,node y)
{
	return x.y==y.y?x.x<y.x:x.y<y.y;
}
void add(int x,int y)
{
	while(x<=n)
	{
		c[x]+=y;
		x+=lowbit(x);
	}
}
int getsum(int x)
{
	int sum=0;
	while(x)
	{
		sum+=c[x];
		x-=lowbit(x);
	}
	return sum;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&b[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&a[i].x,&a[i].y);
		a[i].id=i;
	}
	sort(a+1,a+m+1,cmp);
	int now=1;
	for(int i=1;i<=n;i++)
	{
		if(last[b[i]]) add(last[b[i]],-1);
		last[b[i]]=i;
		add(i,1);
		while(i==a[now].y&&now<=m)
		{
			ans[a[now].id]=getsum(a[now].y)-getsum(a[now].x-1);
			now++;
		}
		if(now==m+1) break;
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	return 0;
}

思路3

回到思路1，方法1這樣的暴力是沒有前途的！我們來考慮一下新的暴力：
一開始指針區間0->0，然后對于一個查詢，我們將Left指針逐步更新成新的L，Right同理。
比如一開始Left=2，Right=3，而當前查詢 L=1,r=5。
那么我們Left-1，并且把Left位置上的數字出現次數+1.
Right+1，把Right位置上的數字出現次數+1，直到Right=5為止。

add(x){  //把x位置的數字加入進來
    cnt[x]++;
    if (cnt[x]==0) ans++;
}
remove(x){  //把x位置的數字移出去
    cnt[x]--;
    if (cnt[x]!=0) ans--;
}

以上面題目為例；這種方法需要離線處理，我們同理來看一下解法：

Left=Right=1; add(1);
ans=0;
for u=1 to m{
    while (Left<L[u]){  remove(Left); Left++;}
    while (Left>L[u]){  Left--; add(Left);}
    while (Right<r[u]){  Right++; add(Right};}
    while (Right>r[u]){  remove(Right); Right--;}
    output ans;
}

這里說明一下，其實remove(Left); Left--; 等等可以直接寫成remove(Left--)等等，這么寫是為了理解。
分析一下時間復雜度，我們可以從Left和Right的移動量來分析：
每一個新的詢問，Left和Right的移動量最大都會是O（N）。所以這樣子的方法時間復雜度仍然是O（NM），而且可能比上面的暴力更慢。
但是莫隊算法的核心，就是從這么一個算法轉變過來的。
現在來介紹一下莫隊算法解決這道題:
對詢問進行分塊，我們知道m個詢問，L和r的范圍都在n以內，我們根據L和r的大小來對詢問分塊。
比如n=9，有以下的詢問：
2 3
1 4
4 5
1 6
7 9
8 9
5 8
6 8
對于n=9，我們以根號n為每個塊block的大小，這里block=3.
那么我們把1_{3分成一組，4}6，7~9.
對于每一個詢問（L，r），我們以L的范圍來決定這個詢問在哪一個塊。
然后每一個獨自的塊內，我們讓詢問r更小的排在更前面。
那么上面的詢問就可以分組成：
(2,3)/(1,4)/(1,6)和
(4,5)/(5,8)/(6,8)和
(7,9)/(8,9)
這一步的排序操作，我們可以在排序的時候加入判斷條件cmp：

bool cmp(node x,node y)
{
    if (block[x.x]==block[y.x])
        return x.r<y.r;        //同一塊的時候
    return x.L<y.L;      //不同一塊的時候
}

排序之后，我們再來分析一下時間復雜度；接下來我們會看到神奇的事情！！
剛才分析此方法的時候，我們是從L和R的偏移量分析的；我們仍然用這種方法來分析。
考慮一下在同一個塊的時候。由于L的范圍是確定的，所以每次L的偏移量是O（√N）
但是r的范圍沒有確定；r的偏移量是O（N）。
那么從一個塊到另一個塊呢?
明顯地，r我們不需要作考慮，仍然是O（N）。
而L明顯最多也是2√N，而且這種情況下，很快就會到下下一塊。所以也是O（√N）
由于有√N（根號N）個塊，所以r的總偏移量是O（N√N）
而M個詢問，每個詢問都可以讓L偏移O（√N），所以L的總偏移量O（M√N）
注意了，時間復雜度分析的時候一定要注意，r的偏移量和詢問數目是沒有直接關系的。
而L則恰恰相反；L的偏移量我們剛才也說明了，它和塊的個數沒有直接關系。
所以總的時間復雜度是：O（(N+M)√N）
很神奇地看到了，我們僅僅改變了一下問題求解的次序，就讓時間復雜度大幅度下降！
當然在這個說明過程中我們也看到了，事實上，莫隊是一個必須離線的算法。
意味著一些題目如果強制在線，那么莫隊就無能為力了。
實現代碼：

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,now;
int p[500010],block[500010],cnt[500010],ans[500010];
struct node{int x,y,id;} a[500010];
bool cmp(node x,node y)
{
	return block[x.x]==block[y.x] ? x.y<y.y : x.x<y.x;
}
void init()
{
	int u=sqrt(n);
	for(int i=1;i<=n;i++)
		block[i]=(i-1)/u+1;
}
void move(int x,int d)
{
	if(d)
	{
		if(!cnt[p[x]]) now++;
		cnt[p[x]]++;
	}
	else
	{
		cnt[p[x]]--;
		if(!cnt[p[x]]) now--;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&p[i]);
	scanf("%d",&m);
	init();
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
		a[i].id=i;
	}
	sort(a+1,a+m+1,cmp);
	int l=0,r=0;
	for(int i=1;i<=m;i++)
	{
		while(l<a[i].x) move(l++,0);
		while(l>a[i].x) move(--l,1);
		while(r<a[i].y) move(++r,1);
		while(r>a[i].y) move(r--,0);
		ans[a[i].id]=now;
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	return 0;
}

莫隊算法小結

莫隊算法的條件
1、不包含修改操作。
2、題目允許離線，也就是允許在所有詢問全部讀入完之后回答所有詢問。
3、不同區間的結果可以互相計算得出。怎么理解這個條件呢？
就上面的問題而言，如果上一次已經回答了[l,r]區間的答案，并且已經存下了[l,r]區間里的所有數值的出現次數，那么如果下面要詢問[l,r+1]的結果，就只要把右指針r向右移一個單位，并將序列的第r+1個數的出現次數++，同時維護當前的答案，也就是說，如果第r+1個數在[l,r]區間內沒有出現，則當前答案++。同樣，對于[l,r?1],[l?1,r][l+1,r]以及其他任何的區間都可以在上一個詢問的基礎上，通過l和r移動指針來求得下一個詢問的答案。如果滿足這樣的條件，就是說不同區間的結果可以互相計算得出。

莫隊算法的流程
可以看出，一次移動指針是O(1)的。于是想到可以回答第1個詢問之后，不斷地移動指針，一個一個移動到后面將要回答的所有區間。
莫隊算法的主要思想就是這樣。同時，莫隊算法利用了可以離線的條件，將詢問按照合理的順序進行求解，實現了O(N√N）的復雜度。
首先，將序列分塊，即分成√n塊，每個塊的大小為√n。
然后，就將詢問按照左端點所在的塊為第一關鍵字，右端點的位置為第二關鍵字進行從小到大排序，這樣，就能像上面那樣不斷移動指針，可以達到O(N√N）的復雜度。

復雜度證明
不妨把左端點在同一個塊內的詢問分成一組。
先考慮右端點的移動次數。由于在同一組詢問內的右端點是遞增的，所以在同一組內，右端點移動了O(n)次。同時在跨越兩個組時，右端點的移動次數也是O(n)，即右端點一共移動了O(N√N）次。
再考慮左端點的移動次數。可以看出，在同一組詢問內，左端點一次移動的次數為O(N√N）次。
再加上在跨越兩個組時，左端點的移動次數也是O(N√N），因此左端點一共移動了O(N√N）次。復雜度得證。

鞏固練習
[BZOJ1878][SDOI2009]HH的項鏈
[BZOJ2038][2009國家集訓隊]小z的襪子
[BZOJ3236][AHOI2013]作業
[BZOJ4540][HNOI2016]序列
[BZOJ4542][HNOI2016]大數