5255 -- 【FJOI2016】神秘数

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

思路有点巧妙啊。

复杂度分析题。

显然，答案就是第一个(i>sum[i])的位置，其中(sum[i])表示所有权值(leq i) 的元素之和。

我们考虑"暴力"。假设现在能连续组成([1,now])之间的任意值，那么我们考虑有没有权值为(now)的元素：如果没有，答案就是(now+1)；否则我们的值域至少扩大了(a_{now+1})（这里(a_{now+1})表示所有的权值为(now+1)的元素和）。然后我们就将新增的值域([now+1,now+1+a_{now+1}])中的所有元素加上，就这样一直迭代下去。

因为每次迭代值域至少扩大一倍，所以最多迭代(log_2(1e9))次。

代码：

#include<bits/stdc++.h>
#define ll long long
#define N 100005

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

int n,m;
int rt[N];
int ls[N*50],rs[N*50];
int sum[N*50];
const int lx=1,rx=1e9;

int tot;
void Insert(int &v,int old,int lx,int rx,int p) {
	v=++tot;
	ls[v]=ls[old];
	rs[v]=rs[old];
	sum[v]=sum[old]+p;
	if(lx==rx) return ;
	int mid=lx+rx>>1;
	if(p<=mid) Insert(ls[v],ls[old],lx,mid,p);
	else Insert(rs[v],rs[old],mid+1,rx,p);
}

int query(int a,int b,int lx,int rx,int l,int r) {
	if(lx>r||rx<l) return 0;
	if(l<=lx&&rx<=r) return sum[b]-sum[a];
	int mid=lx+rx>>1;
	return query(ls[a],ls[b],lx,mid,l,r)+query(rs[a],rs[b],mid+1,rx,l,r);
}

int main() {
	n=Get();
	for(int i=1;i<=n;i++) {
		int a=Get();
		Insert(rt[i],rt[i-1],lx,rx,a);
	}
	m=Get();
	int l,r;
	while(m--) {
		l=Get(),r=Get();
		int now=0,last=0,tem;
		while(1) {
			tem=query(rt[l-1],rt[r],lx,rx,last+1,now+1);
			if(!tem) break;
			last=now+1;
			now+=tem;
		}
		cout<<now+1<<"
";
	}
	return 0;
}

5255 -- 【FJOI2016】神秘数