4299: Codechef FRBSUM

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 756 Solved: 486
[Submit][Status][Discuss]
Description
数集S的ForbiddenSum定义为无法用S的某个子集（可以为空）的和表示的最小的非负整数。
例如，S={1,1,3,7}，则它的子集和中包含0(S’=∅)，1(S’={1})，2(S’={1,1})，3(S’={3})，4(S’={1,3})，5(S’ = {1, 1, 3})，但是它无法得到6。因此S的ForbiddenSum为6。
给定一个序列A，你的任务是回答该数列的一些子区间所形成的数集的ForbiddenSum是多少。
Input
输入数据的第一行包含一个整数N，表示序列的长度。
接下来一行包含N个数，表示给定的序列A（从1标号）。
接下来一行包含一个整数M，表示询问的组数。
接下来M行，每行一对整数，表示一组询问。
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%的数据，1≤N,M≤100000,1≤A_i≤109，1≤A_1+A_2+…+A_N≤109。

我们对于每一个区间试想：
如果当前我们可以凑出 [ 0 , x ]，那么小于等于x+1的值，都会对答案造成贡献值。所以每次我们把答案小于x+1的所有值算出来，如果大于x，就更新右区间，否则已经无法更新了，直接退出即可。

然后每次算时，类似于斐波那契，速度是log的。

然后每个区间的权值，用主席树维护一下即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,a[N],b[N],m,q,rt[N],cnt;
struct node{
	int l,r,sum;
}t[N*20];
void change(int l,int r,int &x,int y,int k){
	x=++cnt; t[x]=t[y]; t[x].sum+=b[k];
	if(l==r)	return ; int mid=l+r>>1;
	if(k<=mid)	change(l,mid,t[x].l,t[y].l,k);
	else	change(mid+1,r,t[x].r,t[y].r,k);
}
int ask(int l,int r,int x,int y,int k){
	if(r==l)	return (t[x].sum-t[y].sum)*(k>=l);
	int mid=l+r>>1;
	if(k<=mid)	return ask(l,mid,t[x].l,t[y].l,k);
	else	return t[t[x].l].sum-t[t[y].l].sum+ask(mid+1,r,t[x].r,t[y].r,k);
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)	scanf("%lld",&a[i]),b[i]=a[i];
	sort(b+1,b+1+n);	m=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++)	a[i]=lower_bound(b+1,b+1+m,a[i])-b;
	for(int i=1;i<=n;i++)	change(1,m,rt[i],rt[i-1],a[i]); 
	cin>>q;
	while(q--){
		int x,y,res=0;	scanf("%lld %lld",&x,&y);
		while(1){
			int id=lower_bound(b+1,b+1+m,res+1)-b;
			if(b[id]!=res+1)	id--; 
			int t=ask(1,m,rt[y],rt[x-1],id);
			if(t<=res)	break;
			else	res=t;
		}
		printf("%lld\n",res+1);
	}
	return 0;
}