「FJOI2016」神秘数

题目链接

题意

一个可重集合 $S$ 的神秘数为最小的不能被 $S$ 任意一子集之和表示的正整数。

给定正整数序列 $a$，每次询问给定 $l,r$，求 $\{a_l,a_{l+1},\dots,a_r\}$ 的神秘数。

思路

先暴力求解区间 $[l,r]$。

先将其升序排序，从左往右遍历。

设目前能表示 $[1,x)$，目前遍历到 $a$。

• 当 $a\leq x$ 时，易得加上数 $a$ 后能表示 $[1,x+a)$；
• 当 $a>x$ 时，$a$ 及其后面的数都无法表示 $x$，所以 $[l,r]$ 的神秘数即为 $x$。

这是 $O(nm\log n)$ 的，考虑优化。

我们可以一次性取出所有目前 $<x$ 的数，设它们的和为 $sum$。

如果 $sum<x$，那无论如何这个数列都表示不出 $x$，神秘数即为 $x$。

否则 $[1,sum]$ 的数都可以表示，$x\gets sum+1$。

复杂度降至 $O((n+m)\log(\max a_i))$ 乘上一个常数（斐波那契数列中第一个 $>\max a_i$ 的数的编号）。

实现

用主席树维护 $sum$。

注意关于空指针的判定。

代码

#include<cstdio>
using namespace std;
const int N=1e5,S=1e9;
int n,m,a[N+1],tot;
struct seg_tree {
    seg_tree *lson,*rson;
    int val;
}t[(N<<5)+1],*root[N+1];
seg_tree *build(seg_tree *ori,int l,int r,int pos)
{
    int num=++tot;
    if(ori!=NULL) {
        t[num]=*ori;
    }
    t[num].val+=pos;
    if(l==r) {
        return &t[num];
    }
    int mid=(l+r)>>1;
    if(pos<=mid) {
        t[num].lson=build(t[num].lson,l,mid,pos);
    } else {
        t[num].rson=build(t[num].rson,mid+1,r,pos);
    }
    return &t[num];
}
int query(seg_tree *from,seg_tree *to,int l,int r,int f,int t)
{
    if(from==NULL) {
        from=::t;
    }
    if(to==NULL) {
        to=::t;
    }
    if((l>=f)&&(r<=t)) {
        return to->val-from->val;
    }
    int mid=(l+r)>>1,res=0;
    if(f<=mid) {
        res+=query(from->lson,to->lson,l,mid,f,t);
    }
    if(t>mid) {
        res+=query(from->rson,to->rson,mid+1,r,f,t);
    }
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {
        scanf("%d",&a[i]);
    }
    root[0]=&(t[tot=1]=seg_tree{t,t,0});
    for(int i=1;i<=n;++i) {
        root[i]=build(root[i-1],1,S,a[i]);
    }
    scanf("%d",&m);
    for(int l,r;m;--m) {
        scanf("%d%d",&l,&r);
        int res=0,tem=0;
        while(tem>=res) {
            res=tem+1;
            tem=query(root[l-1],root[r],1,S,1,res);
        }
        printf("%d\n",res);
    }
    return 0;
}