Description
数集S的ForbiddenSum定义为无法用S的某个子集（可以为空）的和表示的最小的非负整数。
例如，S={1,1,3,7}，则它的子集和中包含0(S’=∅)，1(S’={1})，2(S’={1,1})，3(S’={3})，4(S’={1,3})，5(S' = {1, 1, 3})，但是它无法得到6。因此S的ForbiddenSum为6。
给定一个序列A，你的任务是回答该数列的一些子区间所形成的数集的ForbiddenSum是多少。
Input
输入数据的第一行包含一个整数N，表示序列的长度。
接下来一行包含N个数，表示给定的序列A（从1标号）。
接下来一行包含一个整数M，表示询问的组数。
接下来M行，每行一对整数，表示一组询问。
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%的数据，1≤N,M≤100000,1≤A_i≤10^9，1≤A_1+A_2+…+A_N≤10^9。
Source
线段树 主席树 脑洞题
又是很神奇的结论题？
给定一个数列，假如我们现在可以用数列中的数凑出$[1,x]$范围内的所有数，若是能从数列中再找到一个$[1,x+1]$范围内的数，我们就可以凑出$[1,x+1]$范围的所有数。而如果我们只能再找到大于x+1的数，那么就无法继续凑了，最终答案是x+1 。
按照这个思想，我们可以提取出询问区间内的数，从小到大尝试答案：
设当前可以凑出$[1,res]$范围。统计所有小于等于res+1的数的和sum，若$ sum>=res+1 $，说明我们可以凑出[1,sum]范围的数。
令res=sum，继续尝试扩大范围。
我们发现如果每次区间都能扩大，至少会扩大为原来的两倍，可以在$O(log(n))$的时间内回答一个询问。
具体的查询可以用主席树维护。
1 #include2 #include 3 #include 4 #include 5 #include 6 #define LL long long 7 using namespace std; 8 const int INF=1e9; 9 const int mxn=100010;10 int read(){11 int x=0,f=1;char ch=getchar();12 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}14 return x*f;15 }16 struct node{17 int l,r;int smm;18 }t[mxn*60];19 int rot[mxn],cnt=0;20 #define lc t[rt].l21 #define rc t[rt].r22 void update(int p,int v,int l,int r,int y,int &rt){23 rt=++cnt;24 t[rt]=t[y];25 t[rt].smm+=v;26 if(l==r)return;27 int mid=(l+r)>>1;28 if(p<=mid)update(p,v,l,mid,t[y].l,lc);29 else update(p,v,mid+1,r,t[y].r,rc);30 return;31 }32 int query(int R,int l,int r,int y,int rt){33 if(r<=R){ return t[rt].smm-t[y].smm;}34 int mid=(l+r)>>1;35 if(R<=mid)return query(R,l,mid,t[y].l,lc);36 return query(R,l,mid,t[y].l,lc)+query(R,mid+1,r,t[y].r,rc);37 }38 int n,m;39 int a[mxn];40 int main(){41 int i,j;42 n=read();43 for(i=1;i<=n;i++)a[i]=read();44 for(i=1;i<=n;i++)update(a[i],a[i],1,1e9,rot[i-1],rot[i]);45 m=read();46 int L,R,ans=1;47 while(m--){48 L=read();R=read();int res=1;49 ans=min(INF,query(res,1,1e9,rot[L-1],rot[R]));50 while(ans>=res && res<1e9){51 res=ans+1;52 ans=min(INF,query(res,1,1e9,rot[L-1],rot[R]));53 }54 printf("%d\n",ans+1);55 }56 return 0;57 }