题目描述：

求区间  $mex$ 值. 

题解：用主席树维护每个点出现的最靠右的位置.

当我们查询区间 $[l,r]$ 时，只需看一下 $[0,n]$ 在 $rt[r]$ 的线段树下每个点出现的最靠右的位置的最小值是否小于 $l$

若小于 $l$ ，则一直贪心在线段树上向左走，直到走到叶子节点为止. 

#include
     
      #define maxn 200001  using namespace std;void setIO(string s){	string in=s+".in"; 	freopen(in.c_str(),"r",stdin); }namespace tr{	#define mid ((l+r)>>1) 	#define lson t[x].l	#define rson t[x].r 	struct Node	{		int l,r,minv,val; 	}t[maxn*30]; 	int cnt; 	int newnode() { return ++ cnt; }	void build(int &x,int l,int r)	{		x=newnode(); 		if(l==r) return; 		build(lson,l,mid), build(rson,mid+1,r); 	}	int insert(int u,int l,int r,int k,int delta)	{		int x=newnode(); 		t[x]=t[u];              		if(l==r) 		{ 			t[x].val=t[x].minv=delta; 			return x; 		}    		if(k<=mid) 		{			lson=insert(t[u].l, l, mid, k, delta);     		}		else 		{			rson=insert(t[u].r, mid + 1, r, k, delta);   		}		t[x].minv=maxn+233; 		if(lson) t[x].minv=min(t[x].minv,t[lson].minv); 		if(rson) t[x].minv=min(t[x].minv,t[rson].minv);                  			return x;   	}	int query(int x,int l,int r,int k)	{		if(l==r) return l; 		if(t[lson].minv < k) return query(lson, l, mid, k); 		else return query(rson, mid + 1, r, k);   	}}; int n,Q; int arr[maxn],rt[maxn];   int main(){	int i,j,x,y,l,r;  	// setIO("input"); 	scanf("%d%d",&n,&Q); 	tr::build(rt[0],0,n+1); 	for(i=1;i<=n;++i)	{		scanf("%d",&arr[i]);        		arr[i]=min(arr[i], n + 1);       		rt[i]=tr::insert(rt[i-1],0,n+1,arr[i],i); 	} 	for(i=1;i<=Q;++i)	{		scanf("%d%d",&l,&r); 		printf("%d\n",tr::query(rt[r], 0, n + 1, l));  	}	return 0; }