题目

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

分析

显然，当\(a_i>n\)时，对答案没有影响，所以全部视为n+1。

有两种方法，主席树和权值线段树。

主席树裸题，就讲权值线段树。

首先将询问按r排序，将1~r的\(a_i\)全部加入权值线段树，记录它最晚出现的位置，对于每个区间记录这个区间中每个数最晚出现的位置的最小值mn。

查询一个l，当\(该区间左儿子的mn<l\)，显然左儿子中有个\(a_i\)不在区间[l,r]中，就查询左儿子，否则查询右儿子。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           const int maxlongint=2147483647;const int mo=1000000007;const int N=200005;using namespace std;int a[N],pos[N*5],mn[N*5],n,m,ans[N],lim;struct ddx{ int x,y,z;}re[N];bool cmp(ddx x,ddx y){ return x.y
           
            n) a[i]=n+1; } for(int i=1;i<=m;i++) { scanf("%d%d",&re[i].x,&re[i].y); re[i].z=i; } sort(re+1,re+1+m,cmp); lim=1; for(int i=1;i<=m;i++) { while(re[i].y>=lim) { put(0,n+1,1,a[lim],lim); lim++; } ans[re[i].z]=find(0,n+1,1,re[i].x); } for(int i=1;i<=m;i++) { printf("%d\n",ans[i]); }}