# 【BZOJ3339】Rmq Problem

7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7

3
0
3
2
4

BZOJ 3339

## 代码 Code

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define inf 0x7fffffff
struct tnode
{
int l,r,mex;
};
struct question
{
int l,r,id;
}q[200001];
tnode tree[1000000];
int a[200001],tmex[200001],ans[200001],next[200001],c[200001];
bool b[200001];
int i,j,t,n,m,k,p,z,y,x,last;
void build(int k,int tl,int tr)
{
int i,j,t,mid;
tree[k].l=tl;tree[k].r=tr;tree[k].mex=inf;
if (tl==tr)
{
tree[k].mex=tmex[tl];
return ;
}
mid=(tl+tr)>>1;
build(k<<1,tl,mid);
build(k<<1|1,mid+1,tr);
}
bool comp(question a,question b)
{
if (a.l!=b.l) return (a.l<b.l);
else if (a.r!=b.r) return a.r<b.r;
else return a.id<b.id;
}
void change(int s)
{
int i,j,t,end;
t=a[s];
tmex[s]=0;
end=next[s];
if (end==0) end=n;
for (i=end;i>s;i--)
{
if (tmex[i]>t) tmex[i]=t;
else break;
}
}
int main()
{
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
memset(b,false,sizeof(b));
for (i=1;i<=n;i++)
{
if (b[a[i]]) next[c[a[i]]]=i-1;
else next[c[a[i]]]=n;
c[a[i]]=i;
b[a[i]]=true;
}
t=0;
memset(b,false,sizeof(b));
for (i=1;i<=n;i++)
{
b[a[i]]=true;
while (a[i]==t || b[t]) t++;
tmex[i]=t;
}
build(1,1,n);
for (i=1;i<=m;i++)
{
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+1,q+m+1,comp);
last=1;
for (i=1;i<=m;i++)
{
if (q[i].l==last)
{
ans[q[i].id]=tmex[q[i].r];
}
else
{
for (j=last;j<q[i].l;j++) change(j);
ans[q[i].id]=tmex[q[i].r];
}
last=q[i].l;
}
for (i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}``````