普通莫队

Ayaka-T / 2023-07-24 / 原文

普通莫队

形式

如果从$[l，r]$ 的答案能够$ O(1)$扩展到 $[l+1，r][l-1，r][l，r+1][l，r-1]$（即与$[l，r]$相邻的区间）的答案，那么使用莫队算法可以在$O(n\sqrt n)$的复杂度内求出所有询问的答案。

核心

我们假设已经知道$[l,r]$的答案，现在我们要求$[l',r']$,我们就可以移动左右指针，从而计算出答案

但是这可以被卡到$O(n)$

因此我们考虑进行离线处理

我们对$l$的数值进行分块，一共分成$\sqrt n$段，每一段的编号相同

第一关键字是段的编号，第二关键字是右端点的编号

然后我们就可以暴力了

时间复杂度

参考普通莫队算法 - OI Wiki (oi-wiki.org)

细节问题

1，$l$要为1，$r$要为0

2，分块时注意第一关键字，分不好就会TLE

3，询问间区间的转移，我们最好先扩大区间，再缩小区间，避免出现问题

2339 Toys "R" Us - PCOI Online Judge (pcoij8.ddns.net)

题目大意

询问$[l,r]$中第一个没有出现的正整数

做法

一眼莫队，对于寻找第一个没出现的正整数，我们考虑用set查询

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int cnt[maxn],a[maxn],ans[maxn];
set<int>Set;
int n,m,l,size;
struct node{
	int x,y,id;
}q[maxn];
bool cmp(node x,node y){
	if(x.x/size==y.x/size)return x.y<y.y;
	return x.x/size<y.x/size;
}
void update(int now,int whi){
	if(whi==1){
		cnt[a[now]]++;
		if(cnt[a[now]]==1){
			Set.erase(a[now]);
		}
	}
	else{
		cnt[a[now]]--;
		if(!cnt[a[now]])
			Set.insert(a[now]);
	}
}
int main(){
	for(int i=1;i<=100001;i++)Set.insert(i);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&q[i].x,&q[i].y);
		q[i].id=i;
	}
	size=sqrt(m);
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		int ql=q[i].x,qr=q[i].y;
		while(r<qr)update(++r,1);
		while(r>qr)update(r--,-1);
		while(l>ql)update(--l,1);
		while(l<ql)update(l++,-1);
		ans[q[i].id]=*Set.begin();
	}
	for(int i=1;i<=m;i++){
		printf("%d\n",ans[i]);
	}
	
	
	return 0;
}