好久没打主席树了，都忘了怎么用了......
假设我们选了一些数能构成[0,x]范围内的所有值，下一个要加的数是k（k<=x+1），那么可以取到[0,x+k]内的所有取值，所以有一种做法：
对于每个询问区间，先排序，依次加入k，k<=x+1时，取到[0,x+k]；k>x+1，则x+1不能取到，就是答案。复杂度O（mnlogn）。
更优做法：
[0,x]拼成，令ans=x+1，统计在[1,x+1]范围内的数之和sum，如果sum>=ans，说明肯定有一个未加入的数在[1，x+1]之内，又令ans=sum+1，继续；否则答案就是ans。
ai之和在1e9之内，用主席树统计sum。复杂度O(n logn log(∑ai))。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=1e5+10,INF=1e9;
4 int n,m,a[N],rt[N],tot=0;
5 struct node{
6 int lc,rc,v;
7 }t[N<<5];
8
9 void insert(int &i,int j,int l,int r,int pos,int k){
10 t[i=++tot]=t[j],t[i].v+=k;
11 if(l==r) return ;
12 int mid=(l+r)>>1;
13 if(pos<=mid) insert(t[i].lc,t[j].lc,l,mid,pos,k);
14 else insert(t[i].rc,t[j].rc,mid+1,r,pos,k);
15 }
16
17 int query(int i,int j,int l,int r,int ql,int qr){
18 if(ql<=l && qr>=r) return t[j].v-t[i].v;
19 int mid=(l+r)>>1,res=0;
20 if(ql<=mid) res+=query(t[i].lc,t[j].lc,l,mid,ql,qr);
21 if(qr>mid) res+=query(t[i].rc,t[j].rc,mid+1,r,ql,qr);
22 return res;
23 }
24
25 int main(){
26 scanf("%d",&n);
27 for(int i=1;i<=n;i++){
28 scanf("%d",&a[i]);
29 insert(rt[i],rt[i-1],1,INF,a[i],a[i]);
30 }
31 scanf("%d",&m);
32 while(m--){
33 int l,r,ans=1;scanf("%d%d",&l,&r);
34 while(1){
35 int res=query(rt[l-1],rt[r],1,INF,1,ans);
36 if(res>=ans) ans=res+1;
37 else break;
38 }
39 printf("%d\n",ans);
40 }
41 return 0;
42 }
