「学习笔记」莫队算法
0x10 莫队算法的概念
莫队算法是由莫涛提出的算法。莫队算法可以解决一类离线区间询问问题,适用性极为广泛。同时将其加以扩展,便能轻松处理树上路径询问以及支持修改操作。 ——摘自
0x20 普通莫队算法
-
0x21 形式
给定一个序列
Q ,我们设n 和m 同阶。对于序列上的查询问题,给定查询区间[L_i,R_i] ,我们可以以O(1) 的速度扩展答案到与查询区间相邻的四个区间,即:[L_{i-1}, R] ,[L_{i+1}, R] ,[L_i, R_{i+1}] 和[L_i,R_{i-1}] 。 这样,我们实现的时间复杂度就是O(n× 块长) 。而我们通常设的块长为\sqrt{n} ,那么我们的时间复杂度就是O(n\sqrt{n}) ,这对于我们n 达到10^5 时,是一个非常快速的做法,且代码实现较易。代码模板如下:
for (int i = 1; i <= m; i ++) { while (r < mt[i].r) add (++ r); while (l > mt[i].l) add (-- l); while (l < mt[i].l) del (l ++); while (r > mt[i].r) del (r --); ans[mt[i].id] = res; }
-
0x22 实现
对于
m 个询问,我们将其先存储起来,然后再排序,最后离线处理这些数据。 -
0x23 排序
正常来说,我们的排序方法都是以
[L_i, R_i] 所在的块的编号为第一关键字,以右端点为第二关键字从小到大排序。代码实现如下:
inline bool cmp (MOTEAM x, MOTEAM y) { if (block[x.l] == block[y.l]) { //x和y的左端点都在同一个块中时,按右端点进行排序。 return x.r < y.r; } if (block[x.l] != block[y.l]) { //x和y的左端点不在同一个块中时,按左端点进行排序。 return x.l < y.l; } }
-
0x24 优化
在很多时候,我们会盲目的将块长设置为
\sqrt{n} ,所以如果遇到m 和\sqrt{n} 同阶时,而恰好我们将块长设置为\sqrt{n} 时,这样我们就有可能被构造出的数据卡掉。那我们应该将块长设为什么呢?在随机数据下,设为
\frac{n}{\sqrt{\frac{2}{3} m}} 会快一些,大概能优化\frac{1}{10} 左右。证明留给读者自行探索。我们发现,莫队算法实际上看上去仅仅是暴力的优化。但是为什么使用这种"看似暴力"的做法却可以通过高难度数据结构题目呢?很显然,我们的算法复杂度在离线进行排序的时候被优化了。所以,这一排序节省了我们很多的时间。
于是又有神仙创造出了一种新的排序方法:奇偶性排序。
首先,我们原来的排序方法,虽然让右端点的大跳动减少了很多。但是,右端点的跳动依旧存在,使我们的时间复杂度大幅度升高。我们能否创造一种方法排序使其更优化呢?
我们在选择奇数块时,按照右端点从小到大排序,在偶数块时从大到小排序,这样可以减少右端点进行大跳动的次数。
而为什么这样排序会快呢?是因为右指针移动到右边后就不需要跳回左边了,而跳回左边后处理下一个块是要跳动到右边的。很明显,这样就会优化近一半的时间复杂度。
代码实现如下:
inline bool cmp (MOTEAM x, MOTEAM y) { return block[x.l] == block[y.l] ? (block[y.l] & 1) ? x.r < y.r : x.r > y.r : x.l < y.l }
0x30 普通莫队算法例题
-
0x31 例题
1 P1972 [SDOI2009]HH的项链
很经典的一道题。这道题求
[L_i,R_i] 区间只出现过一次的数字个数。这样我们的add 和del 函数就很好设计。inline void add (int x) { cnt[a[x]] ++; if (cnt[a[x]] == 1) { res ++; } } inline void del (int x) { cnt[a[x]] --; if (cnt[a[x]] == 0) { res --; } }但是这道题的出题人也许特意卡莫队做法,正常写法应该是
65pts ,会TLE 5 个点。所以我们需要大力卡常!我们运用上面的优化技巧,修改块长,使用奇偶性排序方法,将
add 和del 改成位运算,提前预处理左端点所在块,吸口氧就可以通过该题了。AC CODE
-
0x32 例题
2 SP3267 DQUERY - D-query
这道题和上道题几乎相同,我们只需要用正常的莫队做法就可以通过。
核心代码如下:
inline void add(int x, int &res) { if (num[a[x]] == 0) { //次数未增加前该数次数出现次数为0,就没有出现过,即不重复。 res ++; } num[a[x]] ++; } inline void del(int x, int &res) { num[a[x]] --; if (num[a[x]] == 0) { //次数减少后该数次数出现次数为0,就出现过,个数减少。 res --; } }
-
0x33 例题
3 P2709 小B的询问
我们看到题目,每个数字贡献为出现次数的平方,这样我们的
add 和del 函数就不太好编写。这样我们就需要用到完全平方的小知识解决此题。
即:
(a+1)^2 = a^2+1+2a 于是我们的
add 函数和del 函数有这种写法:inline void add (int x) { ans += cnt[a[x]] * 2 + 1; cnt[a[x]] ++; } inline void del (int x) { ans -= cnt[a[x]] * 2 - 1; cnt[a[x]] --; }但是不要忘记,莫队是暴力美学,当然我们的
add 函数和del 函数也可以暴力模拟。核心代码如下:
inline void add (int x) { memo -= cnt[a[x]] * cnt[a[x]]; cnt[a[x]] ++; memo += cnt[a[x]] * cnt[a[x]]; } inline void del (int x) { memo -= cnt[a[x]] * cnt[a[x]]; cnt[a[x]] --; memo += cnt[a[x]] * cnt[a[x]]; }
-
0x34 例题
4 CF86D Powerful array
-
0x35 例题
5 P3901 数列找不同
模板题要做吐了qwq。
同样是统计区间内出现次数为
1 的数字个数,最后判断出现次数为1 的数字个数是否为该区间所有数字个数就可以了。 核心代码如下:for (int i = 1; i <= q; i ++) { while (l < mt[i].l) del (l ++); while (r < mt[i].r) add (++ r); while (l > mt[i].l) add (-- l); while (r > mt[i].r) del (r --); if (res == mt[i].r - mt[i].l + 1) { ans[mt[i].id] = 1; } }
-
0x36 例题
6 CF617E XOR and Favorite Number
需要稍微了解异或的性质,其实还是一道普通莫队模板题。
题目要求求异或为
k 的子区间个数,我们可以先做一个前缀异或和,运用前缀和的性质,我们求的答案就是R-(L-1) 的答案,为了方便我们可以存储左端点的时候就将其减一。我们进行
add 和del 函数的时候操作的是异或k 后的答案,这样查询的答案也是异或k 后的,就得到了题目要求的答案。核心代码如下:
inline void add (int x) { res += num[(a[x]^k)]; num[a[x]] ++; } inline void del (int x) { num[a[x]] --; res -= num[(a[x]^k)]; } -
0x37 例题
7 P4462 [CQOI2018]异或序列
这是上道题的双倍经验,依旧是存储答案异或
k 后的数字,查询次数也需要查询异或k 的次数,就可以了。 -
0x38 例题
8 CF220B Little Elephant and Array
普通莫队操作。
add 和del 时判断次数是否与元素相同即可。核心代码如下:
inline void add (int x) { if (num[a[x]] == a[x]) { res --; } num[a[x]] ++; if (num[a[x]] == a[x]) { res ++; } } inline void del (int x) { if (num[a[x]] == a[x]) { res --; } num[a[x]] --; if (num[a[x]] == a[x]) { res ++; } }