首页 > 代码库 > 【BZOJ4408】[Fjoi 2016]神秘数 主席树神题

【BZOJ4408】[Fjoi 2016]神秘数 主席树神题

2024-10-15 13:32:39   214人阅读

【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;}

 

【BZOJ4408】[Fjoi 2016]神秘数 主席树神题


联系
我们