题目大意：不带修，查询区间mex
做法：看这数据范围感觉可以$O(Nlog_2N)$或者是$O(Nsqrt N)$
1.线段树（之所以不说是主席树，是因为并没有用到主席树那种用差分提出区间的操作）
查询[L,R]的话就是对第i棵线段树维护每个数字最后一次出现的位置，维护区间最小值，然后对值域[0,1e9]二分，若mn[l,mid]>=L则说明mex在[mid+1,r]，否则说明mex在[l,mid].
时间效率$O(Nlog_2N)$ 空间效率$O(Nlog_2U)$
2.莫队+分块
挖坑
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 inline ll read() { 5 ll x=0,f=1; char ch=getchar(); 6 for(;ch<'0'||ch>'9';ch=getchar()) 7 if(ch=='-')f=-f; 8 for(;ch>='0'&&ch<='9';ch=getchar()) 9 x=x*10+ch-'0'; 10 return x*f; 11 } 12 inline void chkmin( int &a,int b ) { if(a>b) a=b; } 13 inline void chkmax( int &a,int b ) { if(a<b) a=b; } 14 #define _ read() 15 #define ln endl 16 const int N=2e5+5; 17 int n,m,k,tot,a[N],b[N]; 18 int T[N],lc[40*N],rc[40*N],mn[40*N]; 19 inline void insert( int v,int id,int l,int r,int x,int &y ) { 20 y=++tot; mn[y]=mn[x]; 21 if(l==r) { mn[y]=id; return; } 22 lc[y]=lc[x]; rc[y]=rc[x]; 23 int mid=(l+r)/2; 24 if(v<=mid) insert(v,id,l,mid,lc[x],lc[y]); 25 else insert(v,id,mid+1,r,rc[x],rc[y]); 26 mn[y]=min(mn[lc[y]],mn[rc[y]]); 27 } 28 inline int query( int v,int l,int r,int x ) { 29 if(l==r) return l; 30 int mid=(l+r)/2; 31 if(mn[lc[x]]>=v) return query(v,mid+1,r,rc[x]); 32 else return query(v,l,mid,lc[x]); 33 } 34 int main() { 35 n=_; m=_; 36 for( int i=1;i<=n;i++ ) a[i]=_; 37 for( int i=1;i<=n;i++ ) insert(a[i],i,0,1000000000,T[i-1],T[i]); 38 // for( int i=1;i<=n;i++ ) printf("%d ",ask(0,0,100000000,T[i])); 39 while(m--) { 40 int l=_,r=_; 41 // printf("%d ",ask(0,0,k,T[r])); 42 printf("%d ",query(l,0,1000000000,T[r])); 43 } 44 }