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\;\leq\;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
$n,m\;\leq\;10^5,\sum\;a[i]\;\leq\;10^9$
Solution
当$x$为答案时,满足条件$\sum_{a[i]\;\leq\;x}a[i]<x$
枚举$x$,用主席树求和,判断是否合法,若不合法,$x=\sum_{a[i]\;\leq\;x}a[i]$
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100005
#define M 2000005
using namespace std;
typedef long long ll;
struct linetree{
int l,r,s,lc,rc;ll t;
}lt[M];
int a[N],p[N],rt[N],n,m,l,r,siz,cnt,tmp;
inline void bld(int u,int l,int r,int k){
lt[u].l=l;lt[u].r=r;
if(k>=p[l]&&k<=p[r]){
lt[u].s=1;lt[u].t=(ll)(k);
}
if(lt[u].l<lt[u].r){
int mid=lt[u].l+lt[u].r>>1;
lt[u].lc=++cnt;bld(cnt,l,mid,k);
lt[u].rc=++cnt;bld(cnt,mid+1,r,k);
}
}
inline void build(int u,int lst,int l,int r,int k){
lt[u].l=l;lt[u].r=r;
lt[u].s=lt[lst].s+1;lt[u].t=lt[lst].t+(ll)(k);
if(lt[u].l<lt[u].r){
int mid=lt[u].l+lt[u].r>>1;
if(k<=p[mid]){
lt[u].lc=++cnt;
build(cnt,lt[lst].lc,l,mid,k);
if(lt[lst].rc) lt[u].rc=lt[lst].rc;
else{
lt[u].rc=++cnt;
build(cnt,lt[lst].rc,mid+1,r,k);
}
}
else{
lt[u].rc=++cnt;
build(cnt,lt[lst].rc,mid+1,r,k);
if(lt[lst].lc) lt[u].lc=lt[lst].lc;
else{
lt[u].lc=++cnt;
build(cnt,lt[lst].lc,l,mid,k);
}
}
}
}
inline ll ask(int u,int x){
if(!x||!u) return 0;
if(p[lt[u].r]<=x) return lt[u].t;
int mid=lt[u].l+lt[u].r>>1;
if(x<=p[mid]) return ask(lt[u].lc,x);
return lt[lt[u].lc].t+ask(lt[u].rc,x);
}
inline int chk(int u,int x){
if(!x||!u) return 0;
if(p[lt[u].r]<=x) return lt[u].s;
int mid=lt[u].l+lt[u].r>>1;
if(x<=p[mid]) return chk(lt[u].lc,x);
return lt[lt[u].lc].s+chk(lt[u].rc,x);
}
inline void Aireen(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);p[i]=a[i];
}
sort(p+1,p+1+n);
siz=1;
for(int i=2;i<=n;++i)
if(p[i]!=p[i-1]) p[++siz]=p[i];
rt[1]=++cnt;bld(cnt,1,siz,a[1]);
for(int i=2;i<=n;++i){
rt[i]=++cnt;
build(cnt,rt[i-1],1,siz,a[i]);
}
scanf("%d",&m);
while(m--){
scanf("%d%d",&l,&r);
for(ll i=0,s;;i=s+1ll){
s=ask(rt[r],i)-ask(rt[l-1],i);
if(s>=ask(rt[r],p[siz])-ask(rt[l-1],p[siz])){
printf("%lld\n",s+1ll);break;
}
tmp=upper_bound(p+1,p+1+siz,(int)(s+1ll))-p-1;
if(ask(rt[r],p[tmp])-ask(rt[l-1],p[tmp])<s+1ll){
printf("%lld\n",s+1ll); break;
}
}
}
}
int main(){
freopen("mystic.in","r",stdin);
freopen("mystic.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}