基礎莫隊算法，帶修改莫隊算法

什麼是莫隊算法？

莫隊算法是一種離線處理區間查詢的算法，名字的來源是他的發明人莫濤。莫隊算法的核心思想是對所有查詢進行合理的排序，并将本次查詢的結果不斷進行修改以得到下次查詢的結果

離線無修改的莫隊

先看一道例題 BZOJ 1878

給你一個長度為 n n 的整數序列（數字範圍00到 1000000 1000000 ），然後給出 m m 次查詢，第 ii次查詢給出兩個數字 li l i 和 Ri R i 問你序列中 Li L i 和 Ri R i 之間有多少不同的數字

n≤50000,m≤200000 n ≤ 50000 , m ≤ 200000

考慮一個簡單點的問題，假設我們已經知道了 [2,7] [ 2 , 7 ] 區間的答案，我們要求 [3,9] [ 3 , 9 ] 區間的答案，我們該如何求？

最簡單的我們從3到9掃一遍直接求得答案即可,我們還有另外一種方法：直接在 [2,7] [ 2 , 7 ] 的基礎上，消除2位置對結果的影響，再增加8和9位置對結果的影響即可。 當查詢的區間很多，我們就可以使用這種方法進行優化，但是如果相鄰兩次查詢區間重疊的部分很少，或者沒有重疊的話，這種方法甚至比暴力的掃一遍還要糟糕，解決這個問題的方法就是先對查詢的區間進行某種排序來友善我們區間的轉移。

那麼怎麼樣的順序才能友善我們進行查詢呢？

還是先考慮上一個例子 [2,7] [ 2 , 7 ] 區間轉移到 [3,9] [ 3 , 9 ] 區間，我們可以想象兩個指針一開始 L=2，R=7 要查詢 [3,9] [ 3 , 9 ] 區間就要L+=1,R+=2;是以需要變動3次。而我們要估計算法的時間就是估計指針變動的次數，是以我們的目的就是讓變動的次數盡可能少。這裡給出的方法是：把原序列分成 (√n) ( n ) 個塊，每個塊的大小也是 (√n) ( n ) ,排序是首先按查詢的左端點所在塊進行排序，對于左端點在同一塊内的查詢，以右端點升序排列。

複雜度如何呢？

首先每次移動左端點和右端點的複雜度 O(1) O ( 1 ) （特指在這個問題中，因為問題不同的話可能需要更多的時間來維護）。

對于左端點，在塊内是無序的是以,每次查詢是 O((√n)) O ( ( n ) ) ,一共有 m m 次查詢，是以左端點的移動是O(m(√n))O(m(n))

對于右端點，在塊内有序，是以對每個塊是 O(n) O ( n ) ，塊的數量為 (√n) ( n ) ，是以右端點的移動是 O(n(√n)) O ( n ( n ) )

綜上所述，莫隊算法的時間複雜度為 O((n+m)∗(√n)) O ( ( n + m ) ∗ ( n ) ) ，而原本暴力的時間複雜度為 O(n∗m) O ( n ∗ m ) ，莫隊的暴力已經是很優秀的了。

對于上面的題目代碼如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn = ;
const int maxm = ;    //m和n的最大值
int blocks;
struct Query
{
    int l,r,id;     //因為是離線算法是以需要儲存原本的查詢位置
    bool operator < (const Query & a) const
    {
        if(l/blocks==a.l/blocks)    //在同一塊内的話
            return r < a.r;
        return l < a.l;
    }
}q[maxm];

int n,m;
int a[maxn];
int ans[maxm];      //儲存查詢的結果
int cnt[];   //儲存區間内每種貝殼的數量
int res;
void init()
{
    res = ;
    blocks = sqrt(n);
    memset(cnt,,sizeof(cnt));
}
inline void add(int pos)    //加入pos位置
{
    if(!cnt[a[pos]])
        res++;
    cnt[a[pos]]++;
}
inline void del(int pos)    //删除pos位置
{
    cnt[a[pos]]--;
    if(!cnt[a[pos]])
        res--;
}

int main()
{
    while(scanf("%d",&n)!=EOF) {

        init();

        for (int i=; i<=n; ++i) {
            scanf("%d",a+i);
        }
        scanf("%d",&m);
        for (int i=; i<m; ++i) {
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].id = i;
        }

        sort(q,q+m);

        int L,R;
        L = R = ;
        add();
        for (int i=; i<m; ++i) {
            while(L>q[i].l) add(--L);
            while(R<q[i].r) add(++R);
            while(L<q[i].l) del(L++);
            while(R>q[i].r) del(R--);
            ans[ q[i].id ] = res;
        }

        for (int i=; i<m; ++i) {
            printf("%d\n",ans[i]);
        }
    }
    return ;
}
           

帶單點修改的莫隊

還是一道例題 BZOJ 2120

題目大意和上一題類似，隻是在查詢的過程中會有單點修改的操作，也就是邊修改邊查詢。因為莫隊算法本身是需要離線的，是以如果帶修改的話隻是上面的肯定不能夠使用。

但是也沒有難倒大佬們：如果說之前的基礎莫隊是二維平面的話，那麼我們隻要增加一個次元來表示時間即可。整個解決的過程大緻不變，這裡我們把每個塊的大小定為 n23 n 2 3 ,共分成 n13 n 1 3 塊，排序時先按照左端點所在塊進行排序，塊相同則按照右端點升序排列，如右端點也相同則按照時間進行排序。如果查詢的時候發現目前時間在查詢時間之前，那麼我們就先執行修改操作直到時間相同，相應的如果發現目前時間在查詢時間之後，就要執行反向的修改操作直到時間吻合。覺得抽象的話還是閱讀代碼吧，代碼應該還是比較直覺的。

時間複雜度是 O(n53) O ( n 5 3 ) ，證明還是略了 -·-

#include<bits/stdc++.h>
using namespace std;
const int maxn = ;
int n,m;
int a[maxn];        //記錄顔色的數組
int upcol[maxn];    //第i次更新的顔色
int uppos[maxn];    //第i次更新的位置
int precol[maxn];   //第i次更新前的顔色，用來反向更新
int ans[maxn];      //第i次查詢的結果
int vis[];   //記錄第i種顔色的數量
int now = ;        //目前執行到第幾次修改
int res = ;        //記錄結果
int M,T;            //M詢問的次數，T修改的次數
struct Node
{
    int l,r,x,id;
    Node(){}
    Node(int a,int b,int c,int d) {
        l=a; r=b; x=c; id=d;
    }
    bool operator < (const Node&a) const {
        if(l/==a.l/)  //偷懶直接用的常數實際應該是塊的大小
            return r < a.r;
        return l < a.l;
    }
}q[maxn];
inline void add(int pos)
{
    if(!vis[a[pos]]) {
        ++res;
    }
    vis[a[pos]]++;
}
inline void Del(int pos)
{
    vis[a[pos]]--;
    if(!vis[a[pos]]) {
        --res;
    }
}
void upd(int x,int i)   //第X次修改，在第i次查詢
{
    int pos = uppos[x];
    int col = upcol[x];
    precol[x] = a[pos];
    if(q[i].l<=pos&&q[i].r>=pos) {
        vis[a[pos]]--;
        if(!vis[a[pos]])
            --res;
        if(!vis[col])
            ++res;
        vis[col]++;
    }
    a[pos] = col;
}
void Fupd(int x,int i)  //取消第x次修改，在第i次查詢
{
    int pos = uppos[x];
    int col = precol[x];
    if(q[i].l<=pos&&q[i].r>=pos) {
        vis[a[pos]]--;
        if(!vis[a[pos]])
            --res;
        if(!vis[col])
            ++res;
        vis[col]++;
    }
    a[pos] = col;
}
void update(int i)
{
    int tmp = q[i].x;
    while(now<tmp) upd(++now,i);    //把目前時間更新到第i次查詢的時間
    while(now>tmp) Fupd(now--,i);
}
int main()
{
    while(~scanf("%d%d",&n,&m)) {
        for (int i=; i<=n; ++i) {
            scanf("%d",a+i);
        }
        int l,r;
        M = ;
        T = ;
        char op[];
        for (int i=; i<m; ++i) {
            scanf("%s%d%d",op,&l,&r);
            if(op[]=='Q') {
                ++M;
                q[M] = Node(l,r,T,M);
            }
            else {
                uppos[++T] = l;
                upcol[T] = r;
            }
        }
        sort(q+,q+M+);

        now = ;
        res = ;
        memset(vis,,sizeof(vis));
        add();
        l = r = ;
        for (int i=; i<=M; ++i) {
            while(l>q[i].l) add(--l);
            while(r<q[i].r) add(++r);
            while(l<q[i].l) Del(l++);
            while(r>q[i].r) Del(r--);
            update(i);
            ans[q[i].id] = res;
        }
        for (int i=; i<=M; ++i) {
            printf("%d\n",ans[i]);
        }
    }
    return ;
}
           

樹上莫隊

先引入一個叫做括号表示法的東西：

對于下面的一棵樹

這棵樹的括号表示法就是1（2（4，3），5）

然後我們換一種方式把括号替換為他的序号：1244332551 像這樣。

這樣一來我們要查詢一個節點到另一個節點之間的資訊就可以在這個序列做莫隊了。其實我還沒有完全學明白，等以後再繼續更新。

參考了以下大佬們寫的部落格，由衷的感謝

https://www.cnblogs.com/RabbitHu/p/MoDuiTutorial.html

http://blog.csdn.net/xianhaoming/article/details/52201761

http://vfleaking.blog.163.com/blog/static/174807634201311011201627/