题目描述

一个可重复数字集合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]所构成的可重复数字集合的神秘数。

题解

加入我们查询的区间为l-r。

我们先查询有几个1，然后发现有k个，那么然后我们再查询1-k+1有多少数,如果大于等于k+1的话，那么1到k+1都能表出。

重复这个过程即可，最多跳log次。

代码

#include
     
      #include
      
       #define N 100002using namespace std;typedef long long ll;const int maxn=1e9;ll tr[N*32],a[N];int L[N*32],R[N*32],tot,n,m,T[N];inline int rd(){    int x=0;char c=getchar();bool f=0;    while(!isdigit(c)){
   if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x;}void ins(int &cnt,int pre,int l,int r,ll x){    cnt=++tot;    tr[cnt]=tr[pre]+x;L[cnt]=L[pre];R[cnt]=R[pre];    if(l==r)return;    int mid=(l+r)>>1;    if(mid>=x)ins(L[cnt],L[pre],l,mid,x);    else ins(R[cnt],R[pre],mid+1,r,x); }ll query(int cnt,int pre,int l,int r,ll x){//    cout<
       
        <<" "<
        
<<" "<
         
          <<" "<
          
           <<" "<
           
            <<" "<
            
             <
             
              >1;    if(mid