莫队算法

概述

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

例题

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个询问,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,我们以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),这就是莫队算法,具体的证明过程可以看网上的文章

AC代码

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 {
    
    static long ans = 0;
    static int n,m,block;
    static long[] cnt = new long[50001];
    static int[] arr = new int[50001];
    static int[] pos = new int[50001];
    static Query[] q;
    
    public static class cmp implements Comparator<Query> {
        public int compare(Query x,Query y) {
            if(pos[x.l] == pos[y.l])
                return x.r - y.r;
            return x.l - y.l;
        }
    }
    public static class cmp_id implements Comparator<Query> {
        public int compare(Query x,Query y) {
            return x.id - y.id;
        }
    }
    
    static void init() {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        m = cin.nextInt();
        q = new Query[m + 1];
        for(int i = 1;i <= n;i++)
            arr[i] = cin.nextInt();
        block = (int) Math.sqrt(n);
        for(int i = 1;i <= n;i++) 
            pos[i] = (i - 1) / (block + 1);
        for(int i = 1;i <= m;i++) {
            int l = cin.nextInt();
            int r = cin.nextInt();
            q[i] = new Query(l,r,i);
        }
    }
    
    static void solve() {
        for(int i = 1,l = 1,r = 0;i <= m;i++) {
            while(r < q[i].r)
                update(++r,1);
            while(r > q[i].r)
                update(r--,-1);
            while(l < q[i].l)
                update(l++,-1);
            while(l > q[i].l)
                update(--l,1);
            if(q[i].l == q[i].r) {
                q[i].a = 0;
                q[i].b = 1;
                continue;
            }
            q[i].a = ans - (q[i].r - q[i].l + 1);
            q[i].b = (long)(q[i].r - q[i].l + 1) * (q[i].r - q[i].l);
            long k = gcd(q[i].a,q[i].b);
            q[i].a /= k;
            q[i].b /= k;
        }
    }
    
    private static void update(int x,int add) {
        ans -= sqr(cnt[arr[x]]);
        cnt[arr[x]] += add;
        ans += sqr(cnt[arr[x]]);
    }
    
    public static void main(String[] args) {
        init();
        Arrays.sort(q,1,q.length,new cmp());
        solve();
        Arrays.sort(q,1,q.length,new cmp_id());
        for(int i = 1;i <= m;i++)
           System.out.println(q[i].a + "/" + q[i].b);
    }

    private static long sqr(long x) {
        return x * x;
    }
    private static long gcd(long a,long b) {
        return b == 0 ? a : gcd(b,a % b);
    }
}

莫队算法

 莫队的精髓就在于,离线得到了一堆需要处理的区间后,合理的安排这些区间的计算次序以得到一个较优的复杂度

复杂度分析
  • 分块相同时,右端点递增是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 arrayXOR and Favorite Number

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏令仔很忙

限制字符串输入——正则表达式(VB.NET)

在做机房收费系统的时候,几乎所有的窗体上都存在着文本框或者组合框,当用户进行操作的时候,首先要判断是否为空,然后再对各种属性进行判断,比如;卡号、学号、金额等...

3021
来自专栏张善友的专栏

在Entity Framework 中执行T-sql语句

从Entity Framework  4开始在ObjectContext对象上提供了2个方法可以直接执行SQL语句:ExecuteStoreQuery<T> 和...

22710
来自专栏HansBug's Lab

1901: Zju2112 Dynamic Rankings

1901: Zju2112 Dynamic Rankings Time Limit: 10 Sec  Memory Limit: 128 MB Submit: ...

2806
来自专栏分布式系统和大数据处理

C#中的委托和事件 - Part.1

文中代码在VS2005下通过,由于VS2003(.Net Framework 1.1)不支持隐式的委托变量,所以如果在一个接受委托类型的位置直接赋予方法名,在V...

1173
来自专栏机器学习入门

LWC 58:724. Find Pivot Index

LWC 58:724. Find Pivot Index 传送门:724. Find Pivot Index Problem: Given an array ...

2028
来自专栏博客园

Core官方DI解析(4)--CallSiteRuntimeResolver

这两个类都在其CallSiteVisitor<TArgument, TResult>基类中

913
来自专栏闵开慧

pig操作与注意事项

grunt> A = load 'hdfs://192.168.0.118:9000/user/hadoop/data.txt' as (name:charar...

2773
来自专栏博客园

Core官方DI解析(4)--CallSiteRuntimeResolver

​ CallSiteRuntimeResolver类型是一个创建或获取服务实例的类型,这个类型继承了CallSiteVisitor<TArgument, TRe...

991
来自专栏Golang语言社区

【Go 语言社区】Golang源码解读之map

golang的map实现并不是像c++一样使用红黑树,而是使用了hashmap,用数组来实现。 详细的实现后续补充,这里先做个备忘。 在iterate整个map...

3073
来自专栏吴伟祥

字节、字符、位 原

字节(Byte /bait/ n. [C])是计算机信息技术用于计量存储容量的一种计量单位,也表示一些计算机编程语言中的数据类型和语言字符。

1073

扫码关注云+社区

领取腾讯云代金券