bzoj 4408: [Fjoi 2016]神秘数 （主席树）

Description

一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13}，1 = 12 = 1+13 = 1+1+14 = 45 = 4+16 = 4+1+17 = 4+1+1+18无法表示为集合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

Sample Output

HINT

对于100%的数据点，n,m <= 100000，∑a[i] <= 10^9

Source

鸣谢yyh上传

题解：主席树

假设我们有一串有序(从小到大)的数，前i个数可以达到的范围是[1,x]，那么如果第i+1个数是y，设y<=x+1,那么我可以得到新的范围是[1,x+y]；如果y>x+1,那么x+1是无论如何都取不到的，我们就找到了答案。

那么这是个暴力的思路，如何在O(nlogn) 的时间求解呢？

区间内的数有序->离散化+线段树的下标表示权值的大小。

还要求区间的有序数前缀和->主席树

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<map>#define N 100003using namespace std;int n,m,a[N],b[N],hash[N],cnt,sz,root[N];struct data{	int l,r,sum;}tr[N*20];void insert(int j,int &i,int l,int r,int x,int v){	i=++sz; tr[i]=tr[j];	tr[i].sum+=v;	if (l==r) return;	int mid=(l+r)/2;	if (x<=mid) insert(tr[j].l,tr[i].l,l,mid,x,v);	else insert(tr[j].r,tr[i].r,mid+1,r,x,v);}int find(int x){	int l=1; int r=cnt; int ans=cnt+1;	while (l<=r) {		int mid=(l+r)/2;		if (b[mid]>x) ans=min(ans,mid),r=mid-1;		else l=mid+1;	}	return ans;}int qjsum(int i,int j,int l,int r,int ll,int rr){	if (ll<=l&&r<=rr) return tr[j].sum-tr[i].sum;	int mid=(l+r)/2; int ans=0;	if (ll<=mid) ans+=qjsum(tr[i].l,tr[j].l,l,mid,ll,rr);	if (rr>mid) ans+=qjsum(tr[i].r,tr[j].r,mid+1,r,ll,rr);	return ans;}map<int,int> mp;int main(){	freopen("clearlove.in","r",stdin);	freopen("clearlove.out","w",stdout);	scanf("%d",&n);	for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];	sort(b+1,b+n+1);	cnt=unique(b+1,b+n+1)-b-1;	for (int i=1;i<=cnt;i++) mp[b[i]]=i;	for (int i=1;i<=n;i++) insert(root[i-1],root[i],1,cnt,mp[a[i]],a[i]);	scanf("%d",&m);	for (int i=1;i<=m;i++) {		int l,r; scanf("%d%d",&l,&r);		int ans=1; bool pd=false;		while (true) {			int pos=find(ans);			int t=qjsum(root[l-1],root[r],1,cnt,1,pos-1);			if (t<b[pos]-1) {				PRintf("%d/n",t+1); pd=true;				break;			}			ans=t+1;			if (pos==cnt+1) break;		}		if (!pd) printf("%d/n",ans);	}}