#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }#define lc x<<1#define rc x<<1|1#define MID (l+r)>>1#define lson l, mid, lc#define rson mid+1, r, rcconst int N=200005, oo=~0u>>1;struct dat { int l, r, id; }q[N];int sg[N], mn[N<<2];void upd(int x, int k) { mn[x]=min(mn[x], k); }void pushdown(int x) {	if(mn[x]!=oo) {		upd(lc, mn[x]);		upd(rc, mn[x]);		mn[x]=oo;	}}void build(int l, int r, int x) {	if(l==r) { mn[x]=sg[l]; return; }	mn[x]=oo;	int mid=MID;	build(lson); build(rson);}void update(int l, int r, int x, int L, int R, int k) {	if(L<=l && r<=R) { mn[x]=min(mn[x], k); return; }	pushdown(x);	int mid=MID;	if(L<=mid) update(lson, L, R, k);	if(mid<R) update(rson, L, R, k);}int query(int l, int r, int x, int k) {	if(l==r) return mn[x];	pushdown(x);	int mid=MID;	if(k<=mid) return query(lson, k);	return query(rson, k);}int a[N], b[N], n, m, tot, vis[N], ans[N], inext[N];void getnext() {	for1(i, 1, n) b[i]=a[i];	sort(b+1, b+1+n); tot=unique(b+1, b+1+n)-b-1;	for1(i, 1, n) a[i]=lower_bound(b+1, b+1+tot, a[i])-b;	for1(i, 1, tot) vis[i]=0;	for3(i, n, 1) inext[i]=vis[a[i]], vis[a[i]]=i;}bool cmp(const dat &a, const dat &b) { return a.l<b.l; }void init() {	int k=0;	for1(i, 1, n) {		if(a[i]<N) vis[a[i]]=1;		while(vis[k]) ++k;		sg[i]=k;	}	build(1, n, 1);	sort(q+1, q+1+m, cmp);	getnext();	int now=1;	for1(i, 1, m) {		int l=q[i].l;		while(now<l) {			int nxt=inext[now];			if(nxt==0) nxt=n;			else --nxt; // printf("now:%d nxt:%d a[now]:%d\n", now, nxt, b[a[now]]);			if(now+1<=nxt) update(1, n, 1, now+1, nxt, b[a[now]]);			++now;		}		ans[q[i].id]=query(1, n, 1, q[i].r);	}	for1(i, 1, m) printf("%d\n", ans[i]);}int main() {	read(n); read(m);	for1(i, 1, n) read(a[i]);	for1(i, 1, m) read(q[i].l), read(q[i].r), q[i].id=i;	init();	return 0;}

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

　　第一行n,m。
　　第二行为n个数。
　　从第三行开始，每行一个询问l,r。

　　一行一个数，表示每个询问的答案。

数据规模和约定

　　对于100%的数据：

　　1<=n,m<=200000

　　0<=ai<=109

　　1<=l<=r<=n

　　对于30%的数据：

　　1<=n,m<=1000

By 佚名提供