【优美的暴力】莫队算法

短命女 2021-12-05 05:17 267阅读 0赞

### 文章目录 ###

*  前言
 *  概念
 *   *  是什么
     *  怎么搞
     *   *  移动指针
         *  分块排序
         *   *  Code
         *  怎么转移
         *   *  Code

# 前言 #

话说为什么莫涛和刘汝佳会研究出这个算法，搞得我这个蒟蒻短暂的OI生涯更加痛苦

还有一件事情，*[提莫队长][Link 1]* 到底是什么梗啊？？为什么大家都在莫名乱入？？

但是这个算法真的很优（bao）美（li）。

听说这个算法是莫队（%%%Orz）在集训（做一道毒瘤多次查询题）的时候想出来的。

不管怎么说，%就对了 **%%%%%**

# 概念 #

## 是什么 ##

在上面已经说过，莫队算法就是前国家队队长（ 这等荣耀我们这种蒟蒻只能Orz了！ ）莫涛（*神犇再次%%%*）在役时想出来的算法。

> 莫队算法是用来处理一类无修改的离线区间询问问题。——（摘自前国家队队长莫涛在知乎上对莫队算法的解释。）

简单来说，**莫队算法就是解决一个长度n的区间中，有m次询问查询的离线（在线？？）算法**

当然这是本蒟蒻的理解，有什么不足请dalao指教哈

据某谷说[莫队可以在线实现][Link 2]，emmm蒟蒻求教。。。（感觉好不容易出来的一丢丢感觉又崩溃了啊）

## 怎么搞 ##

莫队算法最核心的地方就是 —— **分块排序** 加 **移动指针得到答案**

### 移动指针 ###

假设一区间长度 n n n为 100000 100000 100000，有 m = 100000 m = 100000 m=100000次询问，有 l ， r l，r l，r区间，询问该区间内的一些问题（比如XXX出现次数什么的，实在想不到什么例题了先将就吧）  
首先，我们日常暴力yy一下下，然后就会果断发现这会超时，接着我们来思考正解。

不知道为什么像不撞南墙不回头的剧情。。

那么现在我们来想正解*之一*——莫队算法

在这里，我们设两个变量curL和curR来作为已经得到的答案所属的区间两端，再记 c n t cnt cnt数组为出现的次数。然后我们就可以来模拟了。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70]  
首先，忽略我的字迹以及突出。。忽略我的字迹以及突出。。忽略我的字迹以及突出。。

假定这是一个区间，左右端点也已经表明了。而且curL和curR之间的ans也已经算出来了，接下来要干的就是转移。

如果按照爆搜似的转移那么就是每个查询都需要线性走一遍。如果说相差小，并且 m m m小的话，这样干也没问题，但是只要 m m m一大起来，要查询的区间更大的话，显然会T。

但是从 c u r L curL curL变到 c u r L − 1 curL - 1 curL−1和 c u r L + 1 curL + 1 curL\+1只需要 O ( 1 ) O(1) O(1)的复杂度。

但是如果说数据专门防这种的话，意思就是数据左右摇： 1 − 2 ; 1000 − 10000 ; 5 − 10 1 - 2; 1000 - 10000; 5 - 10 1−2;1000−10000;5−10这样的话，还不如直接线性搜算了。

正因为如此，莫队算法的精髓也就体现出来了——

### 分块排序 ###

说起这个分块，大家要记住，一般是分成 n \\sqrt n n块，

我也不知道莫队怎么想的，但是好像基本分块都是 n \\sqrt n n??

上文说到莫队算法之所以被称为“优美的暴力”，就是因为这个分块**排序**，也让莫队算法的基础——移动指针不被针对。

话说这个东西我以前也是半信半疑的，但是就是今天小测一童鞋竟因此而TLE？？。。这使得我对莫队再次Orz Orz Orz

那么该怎么排序呢，**就是如果左端点不在一个块里的话，那么按左端点小的排序。如果在一个块里的话，就按右端点小到大排**

这样排序后，莫队算法的时间复杂度一般会为 O ( n n ) O(n \\sqrt n) O(nn)，至于为什么，大家可以去看看两篇博客：[ 1 1 1][1 1 1], [ 2 2 2][2 2 2]，算是作为了解，毕竟不会考嘛（当然亦可参考[某谷口胡][Link 3]）但是那个奇偶性卡常就算了，亲测无效（不知道是不是 R P RP RP不好）

#### Code ####

struct node{ 
        int l, r, id;
        bool operator < (const node &rhs) const { 
            return (l / siz == rhs.l / siz) ? (r < rhs.r) : (l < rhs.l);
            //siz就是分的块，按照上面说得排序
        }
    }que[N + 5];

### 怎么转移 ###

上面说到过，利用指针转移，那么怎么转移呢？？用 w h i l e while while啊哈哈哈 (逃

牢记一句话：***使 a n s ans ans的区间变大就是 a d d add add，否则就是 r e m o v remov remov，也就是添加和去除***  
先分开来看，首先看 c u r L curL curL，如果令 c u r L + 1 curL + 1 curL\+1的话，就相当于是令区间变小，那么我们就用 r e m o v remov remov

可是因为 c u r L curL curL的值已经存在 a n s ans ans里了，那么要更改就要首先把这个值改变，再++

如果令 c u r L − 1 curL - 1 curL−1的话，就是区间变大，为 a d d add add，而且 c u r cur cur的值我们算过，所以就应该先–,再传值更新。

同理，当curR变成curR - 1时，是令区间变小，而且这个值我们也算过，所以是remov且先更新，在–。

变成curR + 1时，为add，且先++再更新。

话说不会有童鞋不知道四个自加和自减的先后顺序吧？？  
（符号在前面的就先算符号，再传新的值进函数，否则就是先传值，再进函数）会的daolao可以自行跳过。。

#### Code ####

void add (int x){ 
    	(do sth...)
    }
    
    void remov (int x){ 
    	(do sth...)
    }
    
    int main (){ 
    	while (curL < que[i].l)
            remov (a[curL ++]);
        while (curL > que[i].l)
            add (a[--curL]);
        while (curR < que[i].r)
            add (a[++curR]);
        while (curR > que[i].r)
            remov (a[curR--]);
    }

[Link 1]: https://www.baidu.com/s?ie=utf-8&f=8&rsv_bp=1&rsv_idx=1&ch=2&tn=maxthon2&wd=%E6%8F%90%E8%8E%AB%E9%98%9F%E9%95%BF&rsv_pq=fc779eb800023f4c&rsv_t=6f8d6Xgqxqx7AQ8UKh4H5iREZrZ%2bpxLQ2deNCegoFVLonh8cTRdw45U8G3UfSMo&rqlang=cn&rsv_enter=1&rsv_sug3=10&rsv_sug2=0&rsv_dl=tb&inputT=2060&rsv_sug4=2061
[Link 2]: https://shoko.blog.luogu.org/moqueue
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70]: /images/20211205/b25d26263e424b5989b0c82ac0effbfd.png
[1 1 1]: https://blog.csdn.net/qq_39562952/article/details/90376886
[2 2 2]: https://blog.csdn.net/Oakley_/article/details/52233688
[Link 3]: https://www.luogu.org/blog/codesonic/Mosalgorithm