细说简单简单莫队

看来看去，似乎已经好久没有写博客了，今天终于是抽出空来，讲一讲莫队。

莫队算法的基本介绍

在信竞得路上，我们时常遇到一些题目让我们求解一段区间里的颜色个数有多少啊，这个区间内的最大值是多少啊？诸如此类的问题常常让我们这些菜鸡束手无策，所以莫队算法横空出世！

莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前，莫队算法已经在 Codeforces 的高手圈里小范围流传，但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时，只分析了普通莫队算法，但是经过 OIer 和 ACMer 的集体智慧改造，莫队有了多种扩展版本，想什么待修莫队之类的。

离线算法

什么是离线算法呢，简单来说就是先把所有的输入都输入后，在进行这些输入的一定的规律来进行时间复杂度更加低的运算，运用这样的算法除了我们今天要学习的莫队以外，还有像CDQ分治，整体二分等等。

正片——莫队算法

思路

首先对于一个区间 $[l,r]$ 它是可以 $O(1)$ 扩展到 $[l+1,r],[l,r+1]$ 等的位置，那么如果我们把现在所要查询的区间按照这样的规律进行排序，那么我们是不是就可以节省重新计算的时间了？
换句话说，就是在排好序后若 $[l_1,r_1]$ 和 $[l_2,r_2]$ 在一组的话，那么 $[l_2,r_2]$ 就是可以把一部分的答案从 $[l_1,r_1]$ 一步一步暴力的转移过来的。

如果这样进行转移的话，我们就可以在 $\mathcal{O}(n\sqrt{n})$ 的时间复杂度内完成计算。

处理

如何排序

我上述的内容都是建立在已经对要处理的区间进行排序的前提下的，所以我们接下来考虑的就是要怎么排序。

首先一定是对左端点进行排序，然后按照右端点的长短从小到大排序，这是没有问题的对吧。
又因为要保证事件复杂度为 $\mathcal{O}(n\sqrt{n})$ ，所以我们在绝大部分的时候是要把左端点按照 $\sqrt{n}$ 的长度进行分组，也就是是说当 $\frac{l_1}{\sqrt{n}}=\frac{l_2}{\sqrt{n}}$ 的时候，就代表 $l_1$ 和 $l_2$ 是同一组的，此时就按照右端点排序，否则按照左端点排序。

struct Node{
int l,r;
};
k=sqrt(n);
bool cmp(const Node a1,const Node a2){
return a1.l/k==a2.l/k?a1.r<a2.r:a1.l<a2.l;
} 

如何分块

但是这里要注意一个点，如果每次都是将块长分为 $\sqrt{n}$ 的话，在有些时候是不对的，或者说是不优秀的，如下：

我们设 $m$ 为询问次数，$n$ 为总长度，当 $m$ 和 $\sqrt{n}$ 同阶的时候，最优的时间复杂度应该是 $\mathcal{O}(n)$ ，但是如果此时把块长设为了 $\sqrt{n}$ 的话，就会导致时间复杂度为 $\mathcal{O}(n\sqrt{n})$

对于此，我们可以进行如下的分析我们设块长度为 $S$，那么对于任意多个在同一块内的询问，挪动的距离就是 $n$，一共 $\frac{n}{S}$ 个块，移动的总次数就是 $\frac{n^2}{S}$，移动可能跨越块，所以还要加上一个 $mS$ 的复杂度，总复杂度为 $O\left(\frac{n^2}{S}+mS\right)$，我们要让这个值尽量小，那么就要将这两个项尽量相等，发现 $S$ 取 $\frac{n}{\sqrt{m}}$ 是最优的（证明见附¹），此时复杂度为 $O\left(\frac{n^2}{\frac{n}{\sqrt{m}}}+m\left(\frac{n}{\sqrt{m}}\right)\right)=O(2n\sqrt{m})=O(n\sqrt{m})$。

示范代码

int lim=sqrt(n);

bool cmp(const Node a1,const Node a2){
return a1.l/lim==a2.l/lim?a1.r<a2.r:a1.l<a2.l;
} 

sort(v+1,v+1+m,cmp);
int nowl=1,nowr=0,tot=0;
for (int i=1;i<=m;i++){
int l1=v[i].l,r1=v[i].r;
while (nowl>l1){
nowl--;
update():
}
while (nowr<r1){
nowr++;
update();
}
while (nowl<l1){
update():
nowl++;
}
while (nowr>r1){
update();
nowr--;
}
}

莫队的优化

我们来看下面这组的数据

1 1
2 100
3 1
4 100

我们假设块长为2，那么发现他来来回回跑了300次左右，这是因为他在不同的块中反复移动，那么我们这里就可以采用莫队的玄学优化方法——奇偶性优化！
奇偶性优化指的是对于奇数块的询问，$r$ 从小到大排序，对于偶数块排序，则按照 $r$ 从大到小进行排序。这样的话，可以让程序快30%左右！

bool cmp(const Node a1,const Node a2){
if (a1.l/k==a2.l/k){
if (a1.l/k&1)return a1.r<a2.r;//a1.l/k&1 等价于 (a1.l/k)%2==1 
else return a1.r>a2.r;
}else return a1.l/k<a2.l/k;
}

例题

题目传送门——小Z的袜子
这题是比较裸的，可以直接上莫队，关键就是要推出转换的关系。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int INF=5e4+10;
struct f{
ll l,r;
ll id,len;
}v[INF];
ll a[INF],k,tot,cnt[INF];
ll ans1[INF],ans2[INF];

bool cmp(const f a1,const f a2){
return a1.l/k==a2.l/k?a1.r<a2.r:a1.l<a2.l;
}

void add(int x){
cnt[a[x]]++;
if (cnt[a[x]]>=2)
tot+=cnt[a[x]]*(cnt[a[x]]-1)-(cnt[a[x]]-1)*(cnt[a[x]]-2);
}

void del(int x){
cnt[a[x]]--;
if (cnt[a[x]]>0)
tot-=(cnt[a[x]]+1)*(cnt[a[x]])-cnt[a[x]]*(cnt[a[x]]-1);
}
int main(){
int n,m;
cin>>n>>m;
k=sqrt(n);
for (int i=1;i<=n;i++){
cin>>a[i];
}
for (int i=1;i<=m;i++){
cin>>v[i].l>>v[i].r;
v[i].len=(v[i].r-v[i].l+1);
v[i].id=i;
}
sort(v+1,v+1+m,cmp);
int nowl=1,nowr=0;
for (int i=1;i<=m;i++){
int l1=v[i].l,r1=v[i].r;
while (nowl<l1){
del(nowl);
nowl++;
}
while (nowl>l1){
nowl--;
add(nowl);
}
while (nowr<r1){
nowr++;
add(nowr);
}
while (nowr>r1){
del(nowr);
nowr--;
}
if (tot==0){
ans1[v[i].id]=0;
ans2[v[i].id]=1;
}else {
ll A=tot,B=v[i].len*(v[i].len-1);
ll g=__gcd(A,B);
ans1[v[i].id]=A/g,ans2[v[i].id]=B/g;
}
}
for (int i=1;i<=m;i++){
cout<<ans1[i]<<"/"<<ans2[i]<<endl;
}
return 0;
}

---

1. 我们知道均值不等式指 $a+b\ge 2\sqrt{ab}$ ，那么对于 $\frac{n^2}{S}+mS$ 有 $\frac{n^2}{S}+mS\ge 2\sqrt{\frac{n^2}{S}\times mS}=2\sqrt{n^{2}m}=2n\sqrt{m}$
   那么等号当且仅当 $\frac{n^2}{S}=mS$ 的时候取到，解这个方程得到 $S=\frac{n}{\sqrt{m}}$ ↩︎

原文地址：https://blog.csdn.net/CylMK/article/details/144058574

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！