基础莫队算法，带修改莫队算法

什么是莫队算法？

莫队算法是一种离线处理区间查询的算法，名字的来源是他的发明人莫涛。莫队算法的核心思想是对所有查询进行合理的排序，并将本次查询的结果不断进行修改以得到下次查询的结果

离线无修改的莫队

先看一道例题 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/