题目描述

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

输入输出格式

输入格式：

 

第一行n,m。

第二行为n个数。

从第三行开始，每行一个询问l,r。

 

输出格式：

 

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

 

输入输出样例

输入样例#1： 

5 52 1 0 2 13 32 32 41 23 5

输出样例#1： 

12303

说明

对于30%的数据：1<=n,m<=1000

对于100%的数据：1<=n,m<=200000，0<=ai<=10^9，1<=l<=r<=n

题解

　　别看了我的莫队时间复杂度是$O(不能过)$的

　　然而数据太水……比方说$0<=ai<=10^9$，然而我记录出现次数的开了$200000$都能A

　　而且更新答案的时候分分钟卡到$O(n)$

　　于是懒得想正解了能过就行

1 //minamoto 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 using namespace std; 7 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 8 char buf[1<<21],*p1=buf,*p2=buf; 9 template
         
          inline bool cmin(T&a,const T&b){
   return a>b?a=b,1:0;}10 inline int read(){11     #define num ch-'0'12     char ch;bool flag=0;int res;13     while(!isdigit(ch=getc()))14     (ch=='-')&&(flag=true);15     for(res=num;isdigit(ch=getc());res=res*10+num);16     (flag)&&(res=-res);17     #undef num18     return res;19 }20 char sr[1<<21],z[20];int C=-1,Z;21 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}22 inline void print(int x){23     if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;24     while(z[++Z]=x%10+48,x/=10);25     while(sr[++C]=z[Z],--Z);sr[++C]='\n';26 }27 const int N=200005;28 int a[N],num[N],ans[N],rt[N],s,n,m,mn,l,r,k;29 struct node{30     int l,r,id;31     inline bool operator <(const node b)const{32         if(rt[l]!=rt[b.l]) return l
          
           b.r;34 }35 }q[N];36 inline void add(int x){37 ++num[x];while(num[mn]) ++mn;38 }39 inline void del(int x){40 --num[x];if(!num[x]) cmin(mn,x);41 }42 int main(){43 //freopen("testdata.in","r",stdin);44 n=read(),m=read(),s=sqrt(n);45 for(int i=1;i<=n;++i) a[i]=read(),rt[i]=(i-1)/s+1;46 for(int i=1;i<=m;++i)47 q[i].l=read(),q[i].r=read(),q[i].id=i;48 sort(q+1,q+1+m);49 l=1,r=0,mn=0;50 for(int i=1;i<=m;++i){51 while(l>q[i].l) add(a[--l]);52 while(r
           
            q[i].r) del(a[r--]);55 ans[q[i].id]=mn;56 }57 for(int i=1;i<=m;++i) print(ans[i]);58 Ot();59 return 0;60 }