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个询问，每次询问给定一个区间，求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。

Hint

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

Solution

若当前神秘数为Ans，那么[1,Ans-1]都可以表示出来

如果当前加入一个数字a，分两种情况

1. 若a<=Ans，区间变为[1,Ans+a-1]，然后神秘数变成Ans+a
2. 若a>Ans，Ans不变

Ans从1开始计算，每次计算小于Ans的数的和sum，然后Ans更新为sum+1

Code

#include 
    
     #include 
     
      #define N 100010using namespace std;int n,m,A[N],rank[N],tot,T[N],ls[N*40],rs[N*40],s[N*40],Ans,sum;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}void update(int last,int p,int l,int r,int &rt){    rt=++tot;    s[rt]=s[last]+p;    ls[rt]=ls[last],rs[rt]=rs[last];    if(l==r) return;    int m=(l+r)>>1;    if(p<=m) update(ls[last],p,l,m,ls[rt]);    else update(rs[last],p,m+1,r,rs[rt]);}int query(int ss,int tt,int l,int r){    if(l==r) return s[tt]-s[ss];    int m=(l+r)>>1;    if(Ans<=m) return query(ls[ss],ls[tt],l,m);    else return query(rs[ss],rs[tt],m+1,r)+s[ls[tt]]-s[ls[ss]]; }int main(){    n=read();    for(int i=1;i<=n;++i) sum+=(A[i]=read());    for(int i=1;i<=n;++i) update(T[i-1],A[i],1,sum,T[i]);    m=read();    while(m--){        int l=read(),r=read();        Ans=1;        for(;;){            int t=query(T[l-1],T[r],1,sum);            if(t