莫队算法-白红宇

莫队算法

阅读量：3949 次

发布时间：2019-05-24

本文共 950 字，大约阅读时间需要 3 分钟。

莫队算法是一个非常神奇的暴力算法，也是一个很好写的算法。能解决区间询问(区间修该的话可以借助差分数组来把复杂度降到O(m+n)，想学习差分数组的话也可以点击该链接)的问题。

举个例子，给定n个数m次询问，每次询问给定区间[l,r]，对于每次询问，我们都可以由上次求出的区间伸缩得到，比如[l-1,r]通过加上a[l],我们就可以得到区间[l,r]。但是如果给定你这样的m次查询：[1,2]、[n-1,n]、[1,2]、[n-1,n]……我们就得不断地伸缩区间，复杂度更是O(mn)。如何的顺序来觉得处理的先后顺序让我们伸缩区间的次数最少呢？如果我们把所有询问以l从小到大排序，l相等的r小的在前，再进行处理，发现也是不可取的，为什么呢？因为区间并不是每次都是扩张的，还有的是缩小的，比如给定这样的询问[1,2]、[2,n]、[3,4]、[5,n]……类似这样的询问时间复杂度依旧是O(mn)，依旧是不可取的。那么究竟以怎样的顺序处理呢？这时我们想到了分块，对于n个数分成 √n 个块，对于m个询问区间以每个区间的l所在块从小到大排序，l所在块相等的r小的在前，最坏情况下，对于每个块都遍历到序列的最右端,共n个点,所以整个算法的复杂度为O(m√n ) ，这样就大大降低了复杂度，然后我们需要对于一开始的询问顺序输出，对于m次询问我们需要用结构体储存询问区间的l，r，以及询问顺序k，每次处理的答案放在以结构体k为下标的ans数组中，最后依次输出即可。

最后一个洛谷上一个莫队算法的模板题**

代码如下、**

#include
   
    using namespace std;const int maxn=50007;int pos[maxn],a[maxn],cnt[maxn],ans[maxn];int n,m,k,sum;struct node{
       int l,r,id;    bool operator <(const node &w)const{
       if(pos[l]==pos[w.l]) return r
    
     q[i].r) sub(R--);        while(L>q[i].l) add(--L);        while(R

转载地址：http://rngwi.baihongyu.com/

你可能感兴趣的文章