莫隊算法講解 （詳盡版）

莫隊算法我早有耳聞。。可惜前不久才去學習。

但是自己看了看論文，也就1h左右，就能夠全部了解了。

也就是說其實這個算法不難。。

好了，讓我們進入正題。

我們首先來看一道例題：

Description

    有n個數字，給出k，以及m個查詢。

    每次查詢的格式是L，r，求L~r（左右包含）這個區間内數字的出現次數剛好是k的數字種數。

    範圍：n<=30000，k<=n，m<=30000，1<=L<r<=n，數列中元素大小<=n。

    輸入n，k，m，然後n個元素，然後m行查詢，對于每一個詢問，輸出正确的答案。

Example input：

5 2 3

1 2 3 2 2

1 2

2 4

1 5

Example output：

0     //沒有

1     //2

0     //沒有（2太多了，也不算）

我們來考慮一下這題的解法。

首先肯定可以萬能暴力，每次L~r枚舉。時間複雜度O（N*M）。

但是這樣的暴力是沒有前途的！我們來考慮一下新的暴力：

一開始指針區間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]==k) ans++;
}
remove(x){  //把x位置的數字移出去
    cnt[x]--;
    if (cnt[x]==k-1) 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（N*M），而且可能比上面的暴力更慢。

但是莫隊算法的核心，就是從這麼一個算法轉變過來的。

現在來介紹一下莫隊算法解決這道題:

對詢問進行分塊，我們知道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(Query x,Query y){
    if ((x/block)!=(y/block))
        return x.L<y.L;        //不同塊的時候
    return x.r<y.r;      //同一塊的時候
}      

排序之後，我們再來分析一下時間複雜度；接下來我們會看到神奇的事情！！

剛才分析此方法的時候，我們是從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）

很神奇地看到了，我們僅僅改變了一下問題求解的次序，就讓時間複雜度大幅度下降！

當然在這個說明過程中我們也看到了，事實上，莫隊是一個必須離線的算法。

意味着一些題目如果強制線上，那麼莫隊就無能為力了。