解题思路

　　首先直接莫队是能被卡的，时间复杂度不对。就考虑按照值域先进行分块再进行莫队，然后统计答案的时候就暴力扫所有的块，直到一个块内元素不满，再暴力扫这个块就行了，时间复杂度O(msqrt(n))

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
          using namespace std;const int N=200005;const int SIZ=600; inline int rd(){    int x=0,f=1;char ch=getchar();    while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();    while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();    return f?x:-x;} int n,m,a[N],bl[N],siz,l[SIZ],r[SIZ],cnt[N],sum[SIZ],ans[N],num; struct Query{    int ql,qr,id;    friend bool operator<(const Query A,const Query B){        if(A.ql/siz!=B.ql/siz) return A.ql
         
          B.qr; return A.qr
          
           n) return; cnt[a[x]]--;if(!cnt[a[x]]) sum[bl[a[x]]]--;}inline void add(int x){ if(a[x]>n) return ; if(!cnt[a[x]]) sum[bl[a[x]]]++;cnt[a[x]]++;}inline int query(){ if(!cnt[0]) return 0;int pos=-1; for(int i=1;i<=num;i++) if(sum[i]!=r[i]-l[i]+1) {pos=i;break;} if(pos==-1) return n+1; for(int i=l[pos];i<=r[pos];i++) if(!cnt[i]) return i;} int main(){ n=rd(),m=rd();siz=sqrt(n)+1;num=n/siz+(n%siz!=0); for(int i=1;i<=n;i++) a[i]=rd(),bl[i]=(i-1)/siz+1; for(int i=1;i<=num;i++) l[i]=(i-1)*siz+1,r[i]=i*siz;r[num]=n; for(int i=1;i<=m;i++) q[i].ql=rd(),q[i].qr=rd(),q[i].id=i; sort(q+1,q+1+m);int L=1,R=0; for(int i=1;i<=m;i++){ while(L
           
            q[i].ql) {L--;add(L);} while(R
            
             q[i].qr) {del(R);R--;} ans[q[i].id]=query(); } for(int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0;}