【BZOJ4408】[Fjoi 2016]神秘数
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<=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
1 2 4 9 10
5
1 1
1 2
1 3
1 4
1 5
Sample Output
2
4
8
8
8
4
8
8
8
HINT
对于100%的数据点，n,m <= 100000，∑a[i] <= 10^9
题解：又是神题啊~
先考虑一种较暴力的方法，我们将[l,r]中的数都拿出来排好序，然后假如我们用前i个数已经能组合出[1,x]的所有数，那么假设设第i+1个数是y，如果y<=x+1，那么我们可以进而组合出[1,x+y]中的所有数；否则，答案就是x+1。
这就需要我们用主席树来维护区间内<=x的所有数的和。然后我们模拟上面的过程。并且容易发现，在这个操作中我们的总和是翻倍式增长的，所以总复杂度只多了一个log。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=100010;
const int inf=1000000000;
int n,m,tot,ans;
struct sag
{
int ls,rs,sum;
}s[maxn*35];
int rt[maxn];
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
void insert(int x,int &y,int l,int r,int pos)
{
if(l>r) return ;
y=++tot;
s[y].sum=s[x].sum+pos;
if(l==r) return ;
int mid=l+r>>1;
if(pos<=mid) s[y].rs=s[x].rs,insert(s[x].ls,s[y].ls,l,mid,pos);
else s[y].ls=s[x].ls,insert(s[x].rs,s[y].rs,mid+1,r,pos);
}
int query(int x,int y,int l,int r,int a)
{
if(l==r) return s[y].sum-s[x].sum;
int mid=l+r>>1;
if(a<=mid) return query(s[x].ls,s[y].ls,l,mid,a);
else return s[s[y].ls].sum-s[s[x].ls].sum+query(s[x].rs,s[y].rs,mid+1,r,a);
}
int main()
{
n=rd();
int i,a,b,tmp;
for(i=1;i<=n;i++) a=rd(),insert(rt[i-1],rt[i],0,inf,a);
m=rd();
for(i=1;i<=m;i++)
{
a=rd(),b=rd(),ans=1;
while(1)
{
tmp=query(rt[a-1],rt[b],0,inf,ans);
if(tmp<ans) break;
ans=tmp+1;
}
printf("%d\n",ans);
}
return 0;
}