RT

是不是哪里常数大了，开O2就能过。

求debug。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define maxn 200005
#define BN 400
using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}

int n,m,a[maxn],cnt[maxn],_cnt[maxn],ans[maxn],_Ans;
int L[maxn],R[maxn];

inline int pos(int x) {return (x-1)/BN+1;}

struct ques
{
	int l,r,id;
	bool operator <(const ques &x)const
	{
		if(pos(l)!=pos(x.l)) return pos(l)<pos(x.l);
		return r>x.r;
	}
}querys[maxn];

inline void init()
{
	int tot=n/BN;
	for(int i=1;i<=tot;++i)
	{
		L[i]=(i-1)*BN+1;
		R[i]=i*BN;
	}
	if(R[tot]<n)
	{
		++tot;
		L[tot]=R[tot-1]+1;
		R[tot]=n;
	}
}

inline void Add(int i)
{
	if(i>n+1) return;
	++cnt[i];
}

inline void Del(int i,int &Ans)
{
	if(i>n+1) return;
	--cnt[i];
	if(!cnt[i]) Ans=min(Ans,i);
}

int main()
{
	freopen("P4137.in","r",stdin);
	n=read(),m=read();
	init();
	for(int i=1;i<=n;++i)
		a[i]=read(),Add(a[i]);
	while(cnt[_Ans]) ++_Ans;
	for(int i=1;i<=m;++i)
		querys[i].l=read(),querys[i].r=read(),querys[i].id=i;
	sort(querys+1,querys+m+1);
	for(int i=1,l=1,r=n,_l,las_B=0,Ans,Tmp;i<=m;++i)
	{
		ques &q=querys[i];
		if(pos(q.l)^las_B)
		{
			las_B=pos(q.l);
			while(r<n) Add(a[++r]);
			while(l<L[las_B]) Del(a[l++],_Ans);
			Ans=_Ans;
		}
		if(pos(q.l)==pos(q.r))
		{
			for(int j=q.l;j<=q.r;++j) if(a[j]<=n+1) ++_cnt[a[j]];
			while(_cnt[ans[q.id]]) ++ans[q.id];
			for(int j=q.l;j<=q.r;++j) if(a[j]<=n+1) --_cnt[a[j]];
			continue;
		}
		while(r>q.r) Del(a[r--],Ans);
		Tmp=Ans;
		_l=l;
		while(_l<q.l) Del(a[_l++],Tmp);
		ans[q.id]=Tmp;
		while(_l>l) Add(a[--_l]);
	}
	for(int i=1;i<=m;++i)
		printf("%d\n",ans[i]);
	return 0;
}