主页
Featured image of post ACM学习笔记——莫队算法……

ACM学习笔记——莫队算法……

杂项——离线算法——莫队算法……

文章字数:2792
预计阅读时长: 分钟

简介

属于离线算法中的一种。

用来解决离线区间询问问题,
将其加以扩展后,还可以解决树上路径询问问题和支持修改操作

使用条件

须满足以下条件:

对于区间$[l,r]$,
其查询后的答案,能够在$O(1)$扩展到其相邻区间的答案

即:
$[l-1,r]$、$[l+1,r]$、$[l,r-1]$、$[l,r+1]$这四个区间

实现

如果满足使用条件后,
自然而然就能想到这种解题方法:

根据上一个询问,一步步扩展到当前询问。

这就是莫队算法中最基本的解题思路,
这样一直扩展下去,就能得到所有询问的答案。


但如果就按照题中给的询问顺序,一个个挨着扩展的话,
肯定会造成大量的重复移动操作

e.g.

99 100
1 2
99 100
1 2
99 100

每次lr都会从一端极值移动到另一端极值。

不排序直接求解,易得其复杂度为$O(n^2)$。


因此莫队算法的核心则是:
我们应该怎样对询问排序,使得这一步步扩展的操作次数尽量少。

也就是该如何定义排序算法。

排序算法

1. 直接排序

首先自然而然想到的排序算法就是:

直接按照询问的lr为主次关键字进行排序。

结构体的<定义为:

struct queryType_direct
{
    int l, r, id;

    bool operator<(const queryType_direct &a) const { return l == a.l ? r < a.r : l < a.l; }
    //当l不同时,l小的排在前面;
	//当l相同时,r小的排在前面。
} direct[MAX_M + 5];

但这样排序算法十分粗糙,
其复杂度仍为$O(n^2)$,仅常数小一些而已,
很容易TLE。

复杂度大致计算方式:

以这种排序方法,
l升序,所以移动次数最坏为$n$,
r最坏情况为反复在两端点间移动,移动次数为$\frac{(n-2)n}{2}$(等差数列计算)。

总移动次数最坏为$\frac{n^2}{2}$,
故复杂度为$O(n^2)$。

2. 分块排序

最有效又简单的排序算法。

具体方法为:

将$n$个询问分为$M$个块。

对于同一个块,按照r的大小排序,
对于不同的块,则按照l的大小排序。

结构体的<定义为:

int BLOCK_SIZE;

struct queryType_block
{
    int l, r, id;

    bool operator<(const queryType_block &a) const { return l / BLOCK_SIZE == a.l / BLOCK_SIZE ? r < a.r : l < a.l; }
	//当 l/BLOCK_SIZE == r/BLOCK_SIZE 时,为同一块,按照r的大小排序;  
	//不为同一块时,按照l的大小排序。
} block[MAX_M + 5];

而块的大小BLOCK_SIZE,一般取为$\sqrt{n}$。


虽然看起来很粗糙,与直接排序的区别十分小(就多了个/BLOCK_SIZE),
但其复杂度却能显著的降到$O(n\sqrt{n})$

复杂度计算方式:

OI-Wiki上的证明方法太多了懒得看x,这里用另一种很不严谨的方式来说明orz……

同一块中,询问个数和块的长度均为$\sqrt{n}$,
l最坏情况也为反复在两极值端点间振荡,但端点距离变为了$\sqrt{n}$,移动次数大致为$\sqrt{n}*\sqrt{n}=n$,
r递增,所以最坏情况移动次数为$n$,

跨块的时候,
l最坏移动$\sqrt{n}$次,
r最坏移动$n$次,

所以每一块(同时算上同一块和跨块的移动操作)移动次数大致为$3n+\sqrt{n}$,
一共$\sqrt{n}$块,
故最坏情况,总移动次数为$3n\sqrt{n}+n$。

即复杂度为$O(n\sqrt{n})$。

2.(1). 分块的优化——奇偶化排序

对于这组已排好序的数据: (令:n100,即BLOCK_SIZE为$10$)

1 1
2 100
10 11
11 100

如果就按照这样的顺序进行操作,
在第二步r为$100$后,
执行第三步会跳到$11$,执行第四步又会跳到$100$。

而将顺序改为:

1 1
2 100
11 100
10 3

则能减少从一极值跳到另一极值的情况


也就是说,对于第二种“分块排序”方法:
在执行完某一块跳到下一块的时候,
r会从当前块的最大值唐突移动到下一块的最小值
从则造成多余的移动操作。

而如果将奇数块改为从小到大排序偶数块改为从大到小排序
则在跳块的时候,能很平滑的从这一块最大过渡到下一块最大

这种优化能使程序快$30%$。

结构体的<定义为:

int BLOCK_SIZE;

struct queryType_block_pro
{
    int l, r, id;
    bool operator<(const queryType_block_pro &a) const { return l / BLOCK_SIZE == a.l / BLOCK_SIZE ? (r == a.r ? 0 : (l / BLOCK_SIZE & 1) ^ (r < a.r)) : l < a.l; }
	//这里运用位运算,实现了当为奇数块时从小到大排序,偶数块时从大到小排序。
} block_pro[MAX_M + 5];

注意:需要特判r == a.r的情况!

否则对于两询问$a,b$,
l属于同一奇数块,且r相等的情况,

排序时会同时满足$a<b$和$b<a$,
使得sort()出错。

sort出错原因是因为其要满足严格弱序
有关严格弱序的介绍可以看这里写的「ACM学习笔记:邻项比较排序……」文章中有提及。

理解不了压行写法的话,也可以看OI-Wiki上的不压行写法

3*. 曼哈顿最小生成树排序

其实最优的排序方法,是构造曼哈顿最小生成树

一种方法是把所有区间$[l,r]$看成平面上的点$(l,r)$,并对所有点建立曼哈顿最小生成树,
每次沿着曼哈顿最小生成树的边在询问之间转移答案。

引自:OI-Wiki

但其复杂度其实也是$O(n\sqrt{n})$,
故一般都采用最简单的分块排序。

【个人也完全不会这个排序方法就不写了_(:з」∠)_……

操作次数比较

以莫队模板题“P1494 小Z的袜子”来进行比较。

当$n,m$较大时:

三种排序操作次数对比 - n,m较大
三种排序操作次数对比 - n,m较大

  • “Raw”:未排序直接操作。
  • “Direct”:直接排序。
  • “Block”:分块排序。
  • “Block Pro”:分块排序+奇偶化。

但注意:
分块排序的操作次数不一定恒小于直接排序。

当$n,m$较小时,很有可能反而大于直接排序。

三种排序操作次数对比 - n,m较小
三种排序操作次数对比 - n,m较小

可以发现反而直接排序操作次数更少。

但由于当$n,m$较大时,这种情况几乎不存在,
所以可以不用考虑。

注意事项

排完序后,会破坏原有询问的顺序,
故要加个id变量,来存储原询问的顺序。

移动操作

当排好序过后,关键就是:
如何通过现在求得的$(l,r)$区间的答案$ans$,
一步步移动lr
来求得新区间$(l',r')$的答案$ans'$。


需要先根据题目分析,
来计算出增加或删除某个元素,对答案的影响。

然后用while判断,一步步l++l--r++r--
得到新询问区间的答案。

while的位置很重要,不能随意调换他们的位置。

可以简单记住以下三种正确顺序:

  • l--, r--, r++, l++
  • l--, r++, l++, r--
  • l--, r++, r--, l++

l----l一样,只要l的加减与r的加减顺序对了就行。

有关证明,可见OI-Wiki上的「关于四个循环位置的讨论」

总模板

int BLOCK_SIZE;

struct queryType
{
    int l, r, id;
    bool operator<(const queryType_block_pro &a) const { return l / BLOCK_SIZE == a.l / BLOCK_SIZE ? (r == a.r ? 0 : (l / BLOCK_SIZE & 1) ^ (r < a.r)) : l < a.l; } //分块+奇偶化
} query[MAX_M + 5];

inline void move(int pos, int sign, int &nowAns) //sign=1代表增加,sign=-1代表减少。
{
    // update nowAns
}

void solve()
{
    BLOCK_SIZE = sqrt(n);
    sort(query + 1, query + m + 1);

    int nowL = 1, nowR = 0, nowAns = 0;
#define L query[i].l
#define R query[i].r
#define ID query[i].idid
    for (int i = 1; i <= m; i++)
    {
        while (nowL > L)
            move(--l, 1, nowAns);
        while (nowR < R)
            move(r++, 1, nowAns);
        while (nowL < L)
            move(l++, -1, nowAns);
        while (nowR > R)
            move(--r, -1, nowAns);
        ans[ID] = nowAns;
    }
}

例题