题意：
一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13}，
8无法表示为集合S的子集的和，故集合S的神秘数为8。
现给定n个正整数a[1]..a[n]，m个询问，每次询问给定一个区间[l,r](l<=r)，求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。
咦，神秘数好熟悉啊
那么如何求神秘数就很清楚了，当前$now$，就找$\le now+1$的数
询问区间？难道用主席树嘛
然后看了下题解 发现的确是主席树，每次$\le now$前缀和看看能不能$+1 \ge now$来更新$now$
复杂度？
之前和现在为$a,b$，下次必定加上$a<\ <b$的数。最多$O(log\sum a)$次
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define lc(x) t[x].l
#define rc(x) t[x].r
typedef long long ll;
const int N=1e5+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,Q,a[N],mp[N],m;
inline void inimp(){
sort(mp+,mp++m);
int p=; mp[++p]=mp[];
for(int i=;i<=m;i++) if(mp[i]!=mp[i-]) mp[++p]=mp[i];
m=p;
}
inline int Bin(int v){
int l=,r=m;
while(l<=r){
int mid=(l+r)>>;
if(v==mp[mid]) return mid;
else if(v<mp[mid]) r=mid-;
else l=mid+;
}
return ;
}
struct Node{
int l,r,sum;
}t[N*];
int root[N],sz;
void fIns(int &x,int l,int r,int p){//printf("ins %d %d %d %d\n",x,l,r,p);
t[++sz]=t[x];x=sz;
t[x].sum+=mp[p];
if(l==r) return;
int mid=(l+r)>>;
if(p<=mid) fIns(lc(x),l,mid,p);
else fIns(rc(x),mid+,r,p);
}
int fQue(int x,int y,int l,int r,int ql,int qr){//printf("que %d %d %d %d %d %d\n",x,y,mp[l],mp[r],ql,qr);if(l==4 && r==4 && qr==8) return 0;
if(qr<mp[l] || ql>mp[r]) return ;
if(ql<=mp[l]&&mp[r]<=qr) return t[y].sum-t[x].sum;
else{
int re=,mid=(l+r)>>;
if(ql<=mp[mid]) re+=fQue(lc(x),lc(y),l,mid,ql,qr);
if(mp[mid]<qr) re+=fQue(rc(x),rc(y),mid+,r,ql,qr);
return re;
}
} int main(){
//freopen("in","r",stdin);
n=read();
for(int i=;i<=n;i++) a[i]=mp[++m]=read();
inimp();
//for(int i=1;i<=n;i++) printf("a %d %d\n",a[i],Bin(a[i]));
for(int i=;i<=n;i++) a[i]=Bin(a[i]),root[i]=root[i-],fIns(root[i],,m,a[i]);//puts("endIns");
Q=read();
while(Q--){
int l=read(),r=read();
int now=;
while(true){
int _=fQue(root[l-],root[r],,m,,now);
if(_<now) break;
else now=_+;
}
printf("%d\n",now);
}
}