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]所构成的可重复数字集合的神秘数。Solution
思路蛮神的QAQ
如果有一个集合的神秘数为ans，当我们想要新加入一个数a时可以发现[a,a+ans-1]可以被表示
如果ans<a则[1,ans-1]与[a,a+ans-1]不连续，答案仍是ans
如果ans>=a则神秘数被更新为a+ans
于是可以用这样的方法求神秘数，当∑ai(ai<=ans)>=ans时（也就是说ans不大于排序后的前缀和，说明还有小于等于ans的数可以加入），∑ai(ai<=ans)+1被作为神秘数并且迭代下去，否则答案就是ans
#include#include #include #include #include #define MAXN 100005using namespace std;int n,m,a[MAXN],b[MAXN],rt[MAXN];int tot=0,ls[MAXN*20],rs[MAXN*20],v[MAXN*20];int read(){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar(); } while(c>='0'&&c<='9'){ x=x*10+c-'0';c=getchar(); } return x*f;}void build(int &idx,int l,int r){ tot++,idx=tot;v[idx]=0; if(l==r)return; int mid=(l+r)>>1; build(ls[idx],l,mid); build(rs[idx],mid+1,r);}void insert(int &idx,int last,int l,int r,int pos,int val){ tot++,idx=tot; v[idx]=v[last]+val; ls[idx]=ls[last],rs[idx]=rs[last]; if(l==r)return; int mid=(l+r)>>1; if(pos<=mid)insert(ls[idx],ls[last],l,mid,pos,val); else insert(rs[idx],rs[last],mid+1,r,pos,val);}int query(int a,int b,int l,int r,int L,int R){ if(L<=l&&R>=r)return v[a]-v[b]; int mid=(l+r)>>1; if(R<=mid)return query(ls[a],ls[b],l,mid,L,R); else if(L>mid)return query(rs[a],rs[b],mid+1,r,L,R); else return query(ls[a],ls[b],l,mid,L,R)+query(rs[a],rs[b],mid+1,r,L,R);}int main(){ n=read(); for(int i=1;i<=n;i++)b[i]=a[i]=read(); sort(b+1,b+1+n); int sz=unique(b+1,b+1+n)-b-1; build(rt[0],1,sz); for(int i=1;i<=n;i++) { int pos=lower_bound(b+1,b+1+sz,a[i])-b; insert(rt[i],rt[i-1],1,sz,pos,a[i]); } m=read(); for(int i=1;i<=m;i++) { int l=read(),r=read(); int k=1,pos=upper_bound(b+1,b+1+sz,k)-b-1; int get=query(rt[r],rt[l-1],1,sz,1,pos); while(get>=k) { k=get+1; pos=upper_bound(b+1,b+1+sz,k)-b-1; get=query(rt[r],rt[l-1],1,sz,1,pos); } printf("%d\n",k); } return 0;}