莫队算法

概述

莫队算法是由莫涛提出的算法，可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。

例题

Description：

有n个数字，给出k，以及m个查询。每次查询的格式是L,R，求L~R（左闭右闭）这个区间内数字的出现次数刚好是k的数字种数。

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)。但是这里要是暴力能过我还说什么莫队算法呢？(orz...)

假设一开始，指针区间(0,0)，对于一个查询，我们将指针Left逐步更新成新的L，Right更新成新的R。

比如一开始Left=2,Right=3，而L=1,R=5，那么我们把Left--，并且把新的Left位置上的数字出现次数+1，Right++，把新的Right位置上的数字出现次数+1，直到Right=5为止

remove(x){ //把x位置的数字加入进来
    cnt[num[x]]++;
    if(cnt[num[x]] == k) 
        ans++;
}
add(x){ //把x位置的数字移出去
    cnt[num[x]]--;
    if (cnt[num[x]] == k - 1)
        ans--;
}

然后以上面题目为例；这种方法需要离线处理，我们同理来看一下解法：

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

分析一下时间复杂度，从Left和Right的移动量来分析：每一个新的询问，Left和Right的移动量最大都会是O(N)，所以这样子的方法时间复杂度仍然是O(N*M)，但是莫队算法的核心就是由这么一个算法转变过来的，下面介绍一下如何用莫队算法解决这道题。

首先，对数组进行分块，m个询问，假设n=9，并且有以下的询问：
2 3
1 4
4 5
1 6
7 9
8 9
5 8
6 8

对于n=9，我们以sqrt(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)。这一步的排序操作代码：

public static class cmp implements Comparator<Query> {
    public int compare(Query x,Query y) {
        if((x.L / block) != (y.L / block))//不同块时
            return x.L / block - y.L / block;
        return x.R - y.R;//同一块内时
    }
}

经过分块之后，时间复杂度达到了O(nlogn)，具体的证明过程可以看网上的文章。莫队算法的精髓就在于，离线得到了一堆需要处理的区间后，合理的安排这些区间的计算次序以得到一个较优的复杂度

复杂度分析

• 分块相同时，右端点递增是O(N)的，分块共有$O(N^{0.5})$个，复杂度为$O(N^{1.5})$
• 分块转移时，右端点最多变化N，分块共有$O(N^{0.5})$个，复杂度为$O(N^{1.5})$
• 分块相同时，左端点最多变化$N^{0.5}$，分块转移时，左端点最多变化$2N^{0.5}$ ，共有N个询问，复杂度为$O(N^{1.5})$

普通莫队模板

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class Query {
    int l,r,id;
    long a,b;
    Query(int L,int R,int id) {
        this.l = L;
        this.r = R;
        this.id = id;
    }
}

public class Main {
    
    final static int N = 1 << 21;
    static long nowAns = 0;//当前答案
    static int n,m,block;
    static long[] cnt = new long[N];
    static long[] ans = new long[N];//记录每个答案
    static int[] arr = new int[N];//数组
    static Query[] q = new Query[N];//询问
    
    public static class cmp implements Comparator<Query> {
        public int compare(Query x,Query y) {
            if(x.l / block == y.l / block)
                return x.r - y.r;
            return x.l - y.l;
        }
    }
        
    public static void remove(int x) {
        //根据题目添加
    }

    public static void add(int x) {
        //根据题目修改
    }
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int l = 0,r = -1;
        n = cin.nextInt();//数组长度
        m = cin.nextInt();//询问次数
        block = (int) Math.sqrt(n);//每块的大小
        for(int i = 0;i < n;i++) {
            arr[i] = cin.nextInt();
        }
        for(int i = 0;i < m;i++) {
            int tmp_l = cin.nextInt();
            int tmp_r = cin.nextInt();
            q[i] = new Query(tmp_l - 1,tmp_r - 1,i);//减1是为了将询问转换为下标
        }
        Arrays.sort(q,0,m,new cmp());//sort是左闭右开的区间
        for(int i = 0;i < m;i++) {
            while(l < q[i].l) remove(l++);//移出数字
            while(l > q[i].l) add(--l);//加入数字
            while(r < q[i].r) add(++r);//加入数字
            while(r > q[i].r) remove(r--);//移出数字
            ans[q[i].id] = nowAns;
        }
        for(int i = 0;i < m;i++)
            System.out.println(ans[i]);
    }
}

remove和add函数分别根据题目要求进行修改。看两道例题Powerful array、XOR and Favorite Number