BZOJ4299 & CC FRBSUM：ForbiddenSum & BZOJ4408 & 洛谷4587 & LOJ2174：[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](l<=r)，求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。

这题双倍经验十分妙，解法也十分妙。

能够发现当我们有k个1的时候我们可以表示1~k，却没法表示k+1，此时我们需要一个k+1的数才能继续表示。

令n为k+1数的个数，则我们可以表示1~n*(k+1)+k的数（可以感性证明），继续递归即可。

主席树维护，复杂度O(nlog^2)，因为每次递归一定会使答案*2.

#include<map>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long double dl;

const int N=1e5+;

const int INF=1e9;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct tree{

    int l,r,sum;

}tr[N*];

int n,m,pool,rt[N];

inline void insert(int y,int &x,int l,int r,int k){

    tr[x=++pool]=tr[y];

    tr[x].sum+=k;

    if(l==r)return;

    int mid=(l+r)>>;

    if(k<=mid)insert(tr[y].l,tr[x].l,l,mid,k);

    else insert(tr[y].r,tr[x].r,mid+,r,k);

}

inline int qry(int nl,int nr,int l,int r,int k){

    if(l==r)return tr[nr].sum-tr[nl].sum;

    int mid=(l+r)>>;

    if(k<=mid)return qry(tr[nl].l,tr[nr].l,l,mid,k);

    else return tr[tr[nr].l].sum-tr[tr[nl].l].sum+

                qry(tr[nl].r,tr[nr].r,mid+,r,k);

}

int query(int l,int r){

    int k=,maxn=;

    while(){

        maxn=qry(rt[l-],rt[r],,INF,k+);

        if(k==maxn)return k+;

        k=maxn;

    }

}

int main(){

    n=read();

    for(int i=;i<=n;i++)insert(rt[i-],rt[i],,1e9,read());

    m=read();

    while(m--){

        int l=read(),r=read();

        printf("%d\n",query(l,r));

    }

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

秒客网

BZOJ4299 & CC FRBSUM：ForbiddenSum & BZOJ4408 & 洛谷4587 & LOJ2174：[FJOI2016]神秘数——题解

相关文章