神秘数（bzoj 4408）

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

HINT

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

/*

  用主席树维护某个状态中数值在某个范围内的个数。

*/

#include<cstdio>

#include<iostream>

#define N 100010

using namespace std;

int ch[N*][],sum[N*],a[N],root[N];

int n,m,mx,size;

void add(int pre,int &k,int l,int r,int v){

    if(!k)k=++size;

    sum[k]=sum[pre]+v;

    if(l==r)return;

    int mid=l+r>>;

    if(v<=mid){

        ch[k][]=ch[pre][];

        add(ch[pre][],ch[k][],l,mid,v);

    }

    else {

        ch[k][]=ch[pre][];

        add(ch[pre][],ch[k][],mid+,r,v);

    }

}

int query(int pre,int k,int l,int r,int v){

    if(v>=r) return sum[k]-sum[pre];

    int mid=l+r>>;

    if(v>mid) return sum[ch[k][]]-sum[ch[pre][]]+query(ch[pre][],ch[k][],mid+,r,v);

    else return query(ch[pre][],ch[k][],l,mid,v);

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        scanf("%d",&a[i]),mx=max(mx,a[i]);

    for(int i=;i<=n;i++)

        add(root[i-],root[i],,mx,a[i]);

    scanf("%d",&m);

    for(int i=;i<=m;i++){

        int l,r,ans=;

        scanf("%d%d",&l,&r);

        while(){

            int sum=query(root[l-],root[r],,mx,ans);

            if(sum<ans)break;

            ans=sum+;

        }

        printf("%d\n",ans);

    }

    return ;

}