Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 578  Solved: 360

[][][]

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

Source

思路

主席树+权值线段树

每一树上建成权值线段树；

对于每一个新添入的点，以其数值为关键字，给对于区间增值为其数值；

对于查询操作，将神秘数从1不断扩展；

代码实现

1 #include
      
        2 const int maxn=1e5+10; 3 int n,m,now,ans; 4 int a,b,c; 5 int hd[maxn],ps,t[maxn<<6],ls[maxn<<6],rs[maxn<<6]; 6 void add(int pre,int&suc,int l,int r,int v){ 7     if(!suc) suc=++ps; 8     t[suc]=t[pre]+v; 9     if(l==r) return;10     int mid=l+r>>1;11     if(v<=mid) rs[suc]=rs[pre],add(ls[pre],ls[suc],l,mid,v);12     else ls[suc]=ls[pre],add(rs[pre],rs[suc],mid+1,r,v);13 }14 int sreach(int pre,int suc,int l,int r,int v){15     if(v>=r) return t[suc]-t[pre];16     int mid=l+r>>1;17     if(v<=mid) return sreach(ls[pre],ls[suc],l,mid,v);18     else return t[ls[suc]]-t[ls[pre]]+sreach(rs[pre],rs[suc],mid+1,r,v);19 }20 int main(){21     scanf("%d",&n);22     for(int i=1;i<=n;i++){23         scanf("%d",&a);24         add(hd[i-1],hd[i],1,1e9,a);25     }26     scanf("%d",&m);27     for(int i=1;i<=m;i++){28         scanf("%d%d",&b,&c),ans=1;29         while(1){30             now=sreach(hd[b-1],hd[c],1,1e9,ans);31             if(now