莫队（二）：证明、代码实现和优化

2、复杂度证明

//这里复杂度的证明我也比较迷糊，所以借鉴自大米的博客

1、莫队首先要按照关键字进行排序，众所周知\(sort\)的复杂度是\(O(nlogn)\)。

2、枚举m个答案为\(O(m)\)，设分块大小为unit
分类讨论：

①左指针的移动：若下一个询问的\(l\)与当前询问的\(l\)不在同一个分块，需要经过最多\(2*unit\)步移动到下一个询问的位置，复杂度为\(O(m*unit)\)。
②右指针的移动：只有当\(l\)在同一分块的情况下，\(r\)才是有序的（其他情况下\(r\)会左右横跳，最坏情况下会跳\(n\)次）,\(l\)在同一份块中时，\(r\)是单调递增的，因此枚举完一个块,\(r\)最多需要移动\(n\)次，总共有\(\frac{n}{unit}\)个块，所以复杂度为\(O(n*n/unit)\)。

由于\(n和m\)同级所以可以都用\(n\)表示，那么其总复杂度为\(O(n*unit+n*n/unit+nlogn)\)

由于分块时每个块都分为\(\sqrt n\)的大小，即\(unit=\sqrt n\)，\(nlogn\)与前面的部分为加法关系且\(\sqrt n>logn\)，所以我们得出莫队算法的复杂度为：

\(O(n\sqrt n)\)

3、终于等到你：代码实现

还是这道题目哦！ https://www.luogu.org/problem/SP3267

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RE register
using namespace std;

const int M=1e6+10;
int n,m,l=1,r,now;
int a[M],cnt[M],ans[M],be[M];//我们使用数组be记录每个点在哪一个分块内
struct node{
	int l,r,id;
}q[M];

//莫队的题目往往有大量的输入输出，所以I/O优化十分必要
inline int Read(){
	char ch=getchar();
	int x=0;
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x;
}

void Print(int x){
	if(x>=10)
		Print(x/10);
	putchar(x%10+'0');
}

//结构体以第一第二关键字进行排序
inline bool CMP(node a,node b){
	return be[a.l]==be[b.l]?a.r<b.r:be[a.l]<be[b.l];
}

//加入新的数字
inline void Add(int x){
	if(!cnt[a[x]]) now++;
	cnt[a[x]]++;
}

//删掉退出的数字
inline void Del(int x){
	cnt[a[x]]--;
	if(!cnt[a[x]]) now--;
}

int main(){
	n=Read();
	for(RE int i=1;i<=n;i++)
		a[i]=Read();
	double sq=sqrt(n);
	for(RE int i=1;i<=ceil((double)n/sq);i++)
		for(RE int j=(i-1)*sq+1;j<=i*sq;++j)
			be[j]=i;
	m=Read();//因为我们的结构体用了q这个变量，这里用m代替题面中的q
	for(RE int i=1;i<=m;i++){
		q[i].l=Read();
		q[i].r=Read();
		q[i].id=i;
	}
	sort(q+1,q+m+1,CMP);
	for(int i=1;i<=m;i++){
		while(l<q[i].l) Del(l++);
		while(l>q[i].l) Add(--l);
		while(r<q[i].r) Add(++r);
		while(r>q[i].r) Del(r--);
		ans[q[i].id]=now;
	}
	for(int i=1;i<=m;i++){
		Print(ans[i]);
		putchar('\n');//用输出优化不要忘了换行
	}
	return 0;
}

本题完结撒花

这是没有吸氧气(\(O_2\)优化）的结果

莫队的优化

1、玄学排序法：奇偶性排序法

其实到现在我还是不懂为什么可以这样优化，但它确实有效，肯定是我太弱了！
优化方法：在排序的时候将CMP函数改成

inline bool CMP(node a,node b){
     return (be[a.l]^be[b.l])?be[a.l]b.r;
 }

你看效果多明显，优化掉了10ms呢！

略显尴尬，我听dalao说能优化掉几百毫秒，可能是题目的原因吧。不理，只要时间少了就是有优化，嘤嘤嘤！

2、移动指针的常数压缩

这个想法我第一次写就这么想的，结果被题解带入了Add()和Del()的大坑，听说这个还能优化几百毫秒，我去试试！

结果不错，这样写速度很快，在这里优化掉了20ms，代码量也很好看，所以我贴上来。注意改动的部分在main( )里

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RE register
using namespace std;

const int M=1e6+10;
int n,m,l=1,r,now;
int a[M],cnt[M],ans[M],be[M];//我们使用be记录点在哪一个分块内 
struct node{
	int l,r,id;
}q[M];

//输入输出优化没什么好说的吧，莫队的题目一般I/O都比较大，建议使用I/O优化 
inline int Read(){
	char ch=getchar();
	int x=0;
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x;
}

void Print(int x){
	if(x>=10)
		Print(x/10);
	putchar(x%10+'0');
}

inline bool CMP(node a,node b){
	return (be[a.l]^be[b.l])?be[a.l]<be[b.l]:(be[a.l]&1)?a.r<b.r:a.r>b.r;
}

int main(){
	n=Read();
	for(RE int i=1;i<=n;i++)
		a[i]=Read();
	double sq=sqrt(n);
	for(RE int i=1;i<=ceil((double)n/sq);i++)
		for(RE int j=(i-1)*sq+1;j<=i*sq;++j)
			be[j]=i;
	m=Read();//因为我们struct用了q了所以我们用m代替题面中的q 
	for(RE int i=1;i<=m;i++){
		q[i].l=Read();
		q[i].r=Read();
		q[i].id=i;
	}
	sort(q+1,q+m+1,CMP);
/*	for(int i=1;i<=m;i++){
		while(l<q[i].l) Del(l++);
		while(l>q[i].l) Add(--l);
		while(r<q[i].r) Add(++r);
		while(r>q[i].r) Del(r--);
		ans[q[i].id]=now;
	}*/
	for(int i=1;i<=m;i++){
		int ql=q[i].l,qr=q[i].r;
		while(l<ql) now-=!--cnt[a[l++]];
		while(l>ql) now+=!cnt[a[--l]]++;
		while(r<qr) now+=!cnt[a[++r]]++;
		while(r>qr) now-=!--cnt[a[r--]];
		ans[q[i].id]=now;
	} 
	for(int i=1;i<=m;i++){
		Print(ans[i]);
		putchar('\n');//用输出优化别忘了换行 
	}
	return 0;
}

被注释掉的代码是朴素做法的部分，已经被优化取代掉了。

3、输入输出优化

都学了莫队了I/O优化肯定没问题，我在我的程序里也用到了。用到莫队的题目输入输出量都比较大，I/O优化的效果是非常可观的，建议都用上。

//实在不会可以看我的介绍：输入输出优化