【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

Sample Output

2
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;

}

神秘数