Description
一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13}，
1 = 12 = 1+13 = 1+1+14 = 45 = 4+16 = 4+1+17 = 4+1+1+18无法表示为集合S的子集的和，故集合S的神秘数为8。现给定n个正整数a[1]..a[n]，m个询问，每次询问给定一个区间[l,r](l<=r)，求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。Input
第一行一个整数n，表示数字个数。
第二行n个整数，从1编号。第三行一个整数m，表示询问个数。以下m行，每行一对整数l,r，表示一个询问。Output
对于每个询问，输出一行对应的答案。
Sample Input
5 1 2 4 9 10 5 1 1 1 2 1 3 1 4 1 5
Sample Output
2 4 8 8 8
HINT
对于100%的数据点，n,m <= 100000，∑a[i] <= 10^9
题解：
先考虑答案是怎么来的，把一个区间单独抽出来，把其中的数字排序，设排序之后是a1,a2,a3,a4,a5,a6，让数字自由组合如果出现中断的地方，则这里就是神秘数。
一句话来说，找到最小的一个神秘数相当于找到一个数x，使得小于x的数字加起来的和小于x。举例来说：1 2 4 9 中数字8保证所有比8小的数字加和：1+2+4=7<8 ，所以8是最小的神秘数。
现在考虑怎么求这个数，由于是区间询问，所以可以想到可持久化线段树，每棵树都维护着1~MAX，然后就可以找到[l,r]里比x小的数的加和啦。
再考虑统计答案，答案有可能是1~sum，枚举答案显然不行。如果现在有1~x+1的数字加起来是y，如果y大于x，也即y大于等于x，说明x不是神秘数
可以让x更新为y，比如1 2 4 8 小于9的数字的加和为15，则1~15里的数字都可以表示出来，这可以由第二段的讲解看出来。然后可以用一个while()来表示了。
1 /************************************************************** 2 Problem: 4408 3 User: __abcdef__ 4 Language: C++ 5 Result: Accepted 6 Time:1948 ms 7 Memory:37212 kb 8 ****************************************************************/ 9 10 #include11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 using namespace std;19 typedef long long LL;20 const int maxn=100010;21 int N,M,MAX,SUM,L,R,a[maxn];22 struct Tree{23 int lc,rc,sum;24 }T[3000000];25 int root[maxn],siz;26 inline void insert(int &i,int l,int r,int w){27 T[++siz]=T[i]; i=siz; T[i].sum+=w;28 if(l==r) return ;29 int mid=(l+r)>>1;30 if(w<=mid) insert(T[i].lc,l,mid,w);31 else insert(T[i].rc,mid+1,r,w);32 }33 inline int query(int x,int y,int l,int r,int ll,int rr){34 if(ll<=l&&r<=rr) return T[y].sum-T[x].sum;35 int mid=(l+r)>>1;36 int ans=0;37 if(ll<=mid) ans+=query(T[x].lc,T[y].lc,l,mid,ll,rr);38 if(mid+1<=rr) ans+=query(T[x].rc,T[y].rc,mid+1,r,ll,rr);39 return ans;40 }41 int main(){42 scanf("%d",&N);43 for(int i=1;i<=N;i++){44 scanf("%d",&a[i]);45 MAX=max(MAX,a[i]);46 }47 for(int i=1;i<=N;i++){48 root[i]=root[i-1];49 insert(root[i],1,MAX,a[i]);50 } 51 scanf("%d",&M);52 while(M--){53 scanf("%d%d",&L,&R);54 int nowsum=0,tmpsum=0;55 while(true){56 tmpsum=query(root[L-1],root[R],1,MAX,1,nowsum+1);57 if(tmpsum>nowsum) nowsum=tmpsum;58 else break;59 }60 printf("%d\n",nowsum+1);61 }62 return 0;63 }