Description
一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13}，
1 = 1
2 = 1+1
3 = 1+1+1
4 = 4
5 = 4+1
6 = 4+1+1
7 = 4+1+1+1
8无法表示为集合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
1 2 4 9 10
5
1 1
1 2
1 3
1 4
1 5
Sample Output
2
4
8
8
8
4
8
8
8
HINT
对于100%的数据点，n,m <= 100000，∑a[i] <= 10^9
题意极为简洁。。。。
可以发现这个题需要分析一些性质来判断一个数是否可以被凑出来。一个数被凑出来的时候一定不会用到大于它的数字，只可能会用到小于它的数字。
问题看起来很无序，那么找到一个考虑的顺序，把询问区间内所有的数字从小到大开始考虑。首先看有没有1，如果有，那么1就可以凑出来，同时可以发现如果有x个1，那么1~x都可以凑出来。那么考虑1~x范围内的所有数字，你可发现任何一个非1的数字都可以使我们可以连续表达的数字区间增大了（脑补一个移动的窗口），1~x区间内能表示出的最大数字就是 x+(区间内小于等于x的最大值)。仔细一想这正是一个同构子问题！
每一次都这样做，我们最多会扩大几次考虑范围呢？不难发现只要还有答案成立，这一次扩大之后的考虑范围至少是上一次的两倍，所以最多也就log级别。
于是我们只需要维护区间内小于等于某个数字的和就可以了，开心上一发主席树板子。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cctype>
using namespace std;
const int MAXN=; int N,M,AA[MAXN],rank[MAXN],tot;
struct persistable_segment_tree{
static const int maxn=;
static const int maxm=;
int root[maxm],np,lc[maxn],rc[maxn],sum[maxn];
persistable_segment_tree(){ np=; }
void pushup(int now){ sum[now]=sum[lc[now]]+sum[rc[now]]; }
void build(int &now,int L,int R){
now=++np,lc[now]=rc[now]=sum[now]=;
if(L==R) return;
int m=L+R>>;
build(lc[now],L,m); build(rc[now],m+,R);
}
int copynode(int now){
np++,lc[np]=lc[now],rc[np]=rc[now],sum[np]=sum[now];
return np;
}
void update(int &now,int L,int R,int pos,int v){
now=copynode(now);
if(L==R){ sum[now]+=v; return; }
int m=L+R>>;
if(pos<=m) update(lc[now],L,m,pos,v);
else update(rc[now],m+,R,pos,v);
pushup(now);
}
int query(int xx,int yy,int L,int R,int A,int B){
if(A<=L&&R<=B) return sum[yy]-sum[xx];
int m=L+R>>;
if(B<=m) return query(lc[xx],lc[yy],L,m,A,B);
if(A>m) return query(rc[xx],rc[yy],m+,R,A,B);
return query(lc[xx],lc[yy],L,m,A,B)+query(rc[xx],rc[yy],m+,R,A,B);
}
}st; void data_in()
{
scanf("%d",&N);
for(int i=;i<=N;i++) scanf("%d",&AA[i]);
scanf("%d",&M);
}
void work()
{
memcpy(rank,AA,sizeof(AA));
sort(rank+,rank+N+);
tot=unique(rank+,rank+N+)-rank;
st.build(st.root[],,tot-);
for(int i=;i<=N;i++){
st.root[i]=st.root[i-];
st.update(st.root[i],,tot-,lower_bound(rank+,rank+tot,AA[i])-rank,AA[i]);
}
int l,r,pos,ans,tmp;
for(int i=;i<=M;i++){
scanf("%d%d",&l,&r);
pos=upper_bound(rank+,rank+tot,)-rank-,ans=;
while(pos){
tmp=st.query(st.root[l-],st.root[r],,tot-,,pos);
if(tmp<ans) break;
ans=tmp+;
if(pos==tot-) break;
pos=upper_bound(rank+,rank+tot,ans)-rank-;
}
printf("%d\n",ans);
}
}
int main()
{
data_in();
work();
return ;
}