[FJOI2016]神秘数(脑洞+可持久化)

题目描述

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

题解

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

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

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

代码

#include<iostream>

#include<cstdio>

#define N 100002

using namespace std;

typedef long long ll;

const int maxn=1e9;

ll tr[N*],a[N];

int L[N*],R[N*],tot,n,m,T[N];

inline int rd(){

    int x=;char c=getchar();bool f=;

    while(!isdigit(c)){if(c=='-')f=;c=getchar();}

    while(isdigit(c)){x=(x<<)+(x<<)+(c^);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)>>;

    if(mid>=x)ins(L[cnt],L[pre],l,mid,x);

    else ins(R[cnt],R[pre],mid+,r,x);

}

ll query(int cnt,int pre,int l,int r,ll x){

//    cout<<cnt<<" "<<pre<<" "<<l<<" "<<r<<" "<<tr[cnt]<<" "<<tr[pre]<<endl;

    if(!cnt)return ;

    if(r<=x)return tr[cnt]-tr[pre];

    int mid=(l+r)>>;

    if(mid<x)return tr[L[cnt]]-tr[L[pre]]+query(R[cnt],R[pre],mid+,r,x);

    else return query(L[cnt],L[pre],l,mid,x);

}

int main(){

    n=rd();int m;

    for(int i=;i<=n;++i)a[i]=rd(),ins(T[i],T[i-],,maxn,a[i]);

    m=rd();int l,r;

    while(m--){

        l=rd();r=rd();

    //    cout<<"****"<<endl;

        ll ans=,now=;

        while(ans<=maxn){

        //    cout<<ans<<endl;

            ans=query(T[r],T[l-],,maxn,ans);

        //    cout<<ans<<" "<<now<<endl;

            if(ans<now)break;else now=ans+,ans=now;

        }

        printf("%lld\n",ans+);

    }

    return ;

}