Rmq Problem / mex

题目描述
有一个长度为n的数组{a1,a2,…,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。

输入格式
第一行n,m。

第二行为n个数。

从第三行开始，每行一个询问l,r。

输出格式
一行一个数，表示每个询问的答案。

输入输出样例
输入 #1 复制
5 5
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5
输出 #1 复制
1
2
3
0
3
说明/提示
对于30%的数据：1<=n,m<=1000

对于100%的数据：1<=n,m<=200000，0<=ai<=10^9，1<=l<=r<=n

可以主席树上二分在线查询，也可以主席树离线，当然我肯定选择莫队啦！！！

这种具有区间可加性，而且相邻区间可以O（1） ，修改，故莫队可行。

对于莫队的del，删除元素，我们删除这个元素之后，直接与当前答案取个最小值即可。

对于莫队的add，添加元素，我们添加这个元素之后，判断与当前答案是否相等，若相等就让当前答案一直增加，直到不存在这个元素。

这题不用离散化，因为最多n个元素，所以答案不会大于n，故不会到达1e9

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10;
int n,m,a[N],vis[N],res[N],mi,bl,cl,cr;
struct node{
	int l,r,id;
}t[N];
int cmp(const node &s1,const node &s2){
	return (s1.l/bl==s2.l/bl)?(s1.r<s2.r):(s1.l<s2.l);
}
inline void del(int x){
	if(!(--vis[a[x]]))	mi=min(mi,a[x]);
}
inline void add(int x){
	if((++vis[a[x]])==1){
		int t=a[x];
		if(t==mi){
			while(++t){
				if(!vis[t]){
					mi=t;	return;
				}
			}
		}
	}
}
signed main(){
	scanf("%d %d",&n,&m);	bl=sqrt(n);
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)	scanf("%d %d",&t[i].l,&t[i].r),t[i].id=i;
	sort(t+1,t+1+m,cmp);	cl=1;
	for(int i=1;i<=m;i++){
		int L=t[i].l;	int R=t[i].r;
		while(cl<L)	del(cl++);
		while(cl>L)	add(--cl);
		while(cr<R)	add(++cr);
		while(cr>R)	del(cr--);
		res[t[i].id]=mi;
	}
	for(int i=1;i<=m;i++)	printf("%d\n",res[i]);
	return 0;
}