莫队算法

概述展开目录

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

例题展开目录

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