https://www.lydsy.com/JudgeOnline/problem.php?id=4299
一个可重复数字集合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
对于每个询问，输出一行对应的答案。
题解
A :
将a从小到大排序，设当前神秘数为ans，扫到了a[i]，那么
1. a[i] < ans 时, ans = ans + a[i] ;
2. a[i] > ans时, ans就是最小的神秘数, 跳出循环.
B :
我们也可以发现神秘数简化推法，ans初始为1，那么下一个ans为(sigma (a[i]<=ans) a[i])+1 . （用A部分方法压缩的想法来思考 [ lastans , nowans ) 区间内数的填充）, 能够看出sigma的次数是log级的.
此时我们需要维护的是任意区间内的sigma, 主席树可以实现.
这里的主席树并没有离散化，因为主席树只需要建 n*( log总长 ) 个点, 这样写更方便 ( 常数变大了但是并不是很影响复杂度 ), 离散化也阔以, 不过注意一下查找的时候用upper_bound.
(在这里mark一下lower_bound和upper_bound的方向)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=;
int n,m,cnt=,tot=;
int a[maxn]={},rt[maxn]={};
int sum[maxn*]={},lc[maxn*]={},rc[maxn*]={};
int read(){
int w=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){w=w*+ch-'';ch=getchar();}
return w*f;
}
void Build(int l,int r,int y,int &x,int v){
x=++tot;sum[x]=sum[y]+v;
if(l==r)return;
lc[x]=lc[y];rc[x]=rc[y];
int mid=(l+r)/;
if(v<=mid) Build(l,mid,lc[y],lc[x],v);
else Build(mid+,r,rc[y],rc[x],v);
}
int Query(int l,int r,int x,int y,int v){
if(l==r)return sum[y]-sum[x];
//cout<<sum[y]<<sum[x]<<l<<r<<endl;
int mid=(l+r)/;
if(v<=mid) return Query(l,mid,lc[x],lc[y],v);
else return Query(mid+,r,rc[x],rc[y],v)+sum[lc[y]]-sum[lc[x]];
}
int main(){
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
n=read();
for(int i=;i<=n;i++){a[i]=read();cnt+=a[i];}
for(int i=;i<=n;i++)Build(,cnt,rt[i-],rt[i],a[i]);
m=read();
for(int i=;i<=m;i++){
int l=read();int r=read();
int ans=;
for(;;){
int z=Query(,cnt,rt[l-],rt[r],ans);
//cout<<z<<endl;
if(z<ans)break;
ans=z+;
}
printf("%d\n",ans);
}
return ;
}