题目描述
一个可重复数字集合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]所构成的可重复数字集合的神秘数。
输入
第一行一个整数n，表示数字个数。 第二行n个整数，从1编号。 第三行一个整数m，表示询问个数。 以下m行，每行一对整数l,r，表示一个询问。
输出
对于每个询问，输出一行对应的答案。
样例输入
1 2 4 9 10
5
1 1
1 2
1 3
1 4
1 5
样例输出
4
8
8
8
提示
对于100%的数据点，n,m <= 100000，∑a[i] <= 10^9
很有思维含量的一道主席树，要考虑的问题就是一个序列的神秘数。我们假设已经处理完了前面一些较小数的神秘数ans(ans刚开始是1)，如果小于等于ans的数的和是sum(sum显然一定>=ans-1)。当sum<ans(即sum=ans-1)时，这个序列的神秘数就是ans，因为这些数(即之前所说的那些较小的数)最大能表示ans-1，而剩下数都比ans大，无法表示ans。当sum>=ans时，1~sum的数都能表示，假设比ans小的数中除去那些较小的数剩下的是a1,a2,a3……，那么1~ans-1+a1都能表示(因为ans~ans+a1-1中的任意一个数减a1一定小于ans，即一定能由那些较小的数表示)，这时较小的数与a1的神秘数就是ans+a1。再将a2加进去，那么1~ans+a1+a2-1的数也就都能表示，以此类推就能得到1~sum的数都能表示。每次只要查询主席树上的前缀和与ans判断一下然后再更新ans就好了。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int x,y;
int cnt;
int v[100010];
int a[100010];
int root[100010];
int sum[6000010];
int ls[6000010];
int rs[6000010];
int updata(int pre,int l,int r,int v)
{
int rt=++cnt;
if(l==r)
{
sum[rt]=sum[pre]+a[v];
return rt;
}
ls[rt]=ls[pre];
rs[rt]=rs[pre];
sum[rt]=sum[pre]+a[v];
int mid=(l+r)>>1;
if(v<=mid)
{
ls[rt]=updata(ls[pre],l,mid,v);
}
else
{
rs[rt]=updata(rs[pre],mid+1,r,v);
}
return rt;
}
int query(int x,int y,int l,int r,int k)
{
if(l==r)
{
return sum[y]-sum[x];
}
int mid=(l+r)>>1;
if(k<=mid)
{
return query(ls[x],ls[y],l,mid,k);
}
else
{
return query(rs[x],rs[y],mid+1,r,k)+sum[ls[y]]-sum[ls[x]];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
v[i]=a[i];
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
v[i]=lower_bound(a+1,a+1+n,v[i])-a;
}
for(int i=1;i<=n;i++)
{
root[i]=updata(root[i-1],1,n,v[i]);
}
a[n+1]=1<<30;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
int mx=1;
int ans;
if(upper_bound(a+1,a+2+n,mx)-a-1==0)
{
printf("1\n");
continue;
}
while((ans=query(root[x-1],root[y],1,n,upper_bound(a+1,a+2+n,mx)-a-1))>=mx)
{
mx=ans+1;
}
printf("%d\n",mx);
}
}