看到这个题目后,删除 O(1) 添加 O(n),做法就是遍历区间 [now,n] 但是最后一个点会T
看到有人说值域分块可以过,虽然最后一个点过了,但是前面又过不了了,最后还是要开 O2
void add(int pos) //暴力添加代码
{
int x=a[pos];
if(!vis[x] && now==x){
for(int i=x+1;i<=n+1;i++){
if(!vis[i]){ now=i; break; }
}
}
vis[x]++;
}
const int N=2e5+5;
int n,m;
int i,j,k;
int a[N];
struct Query
{
int l,r;
int id;
void read(){ sdd(l,r); }
}q[N];
int vis[N],ans[N],now;
int block,num,bel[N],tag[(int)1e3],l[(int)1e3],r[(int)1e3];
bool cmp(Query a,Query b)
{
return bel[a.l]^bel[b.l]?a.l<b.l:a.r<b.r;
}
void build()
{
block=sqrt(n); num=n/block;
if(n%block) num++;
for(int i=1;i<=num;i++){
int L=(i-1)*block+1,R=min(block*i,n);
for(int j=L;j<=R;j++) bel[j]=i;
if(i==1) bel[0]=1,l[i]=0;
else l[i]=L;
r[i]=R;
}
for(int i=1;i<=m;i++) q[i].id=i;
sort(q+1,q+1+m,cmp);
}
void add(int pos)
{
int x=a[pos];
vis[x]++; if(vis[x]==1) tag[bel[x]]++;
if(vis[x]==1 && now==x){
for(int i=bel[x];i<=num;i++){
if(tag[i]==r[i]-l[i]+1) continue;
for(int j=l[i];j<=r[i];j++){
if(!vis[j]){ now=j; return ; }
}
}
}
}
void del(int pos)
{
int x=a[pos];
vis[x]--;
if(!vis[x]) now=min(x,now),tag[bel[x]]--;
}
signed main()
{
//IOS;
while(~sdd(n,m)){
for(int i=1;i<=n;i++) sd(a[i]);
for(int i=1;i<=m;i++) q[i].read();
build();
int l=1,r=0; now=0;
for(int i=1;i<=m;i++){
while(q[i].l<l) add(--l);
while(q[i].r>r) add(++r);
while(q[i].l>l) del(l++);
while(q[i].r<r) del(r--);
ans[q[i].id]=now;
//dbg(now);
}
for(int i=1;i<=m;i++) pd(ans[i]);
}
//PAUSE;
return 0;
}