BZOJ4408：[FJOI2016]神秘数

浅谈主席树：https://www.cnblogs.com/AKMer/p/9956734.html

题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=4408

我们先把问题简化，给你一个可重集，求最小的不能被凑出来的正整数。

性质一：假设原集合可以把\([1,num]\)全部凑出来，新加入一个数字\(x\)，就可以凑出\([1,num+x]\)

证明：显然。

性质二：如果你已经可以凑出\([1,num_1]\)，当前集合里权值在\([1,num_1]\)里的所有数的权值和为\(num_2\)，那么你就可以凑出\([1,num_2]\)。

证明：因为性质一。

性质三：如果你由\([1,num_1]\)得到了\([1,num_2]\)且\(num_2>num_1\)，然后由\([1,num_2]\)得到了\([1,num_3]\)且\(num_3> num_2\)，那么\(num_3\geqslant2*num_1\)。

证明：因为由\(num_2\)转到\(num_3\)，增加的数字必然在\([num_1,num_2]\)内，所以\(num_3\geqslant num_1+num_1\)。

因为这两条性质，我们可以将最小的不能凑出的数不断变大，而且是成倍增长的。先钦点不能凑出的数字为\(1\)，然后根据性质二不断变大，时间是\(60*logn\)的。

时间复杂度：\(O(60*mlogn)\)

空间复杂度：\(O(nlogn)\)

代码如下：

#include <cstdio>
using namespace std;

const int maxn=1e5+5;

int n,m,sum;
int a[maxn],rt[maxn];

int read() {
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}

struct tree_node {
    int sum,cnt,ls,rs;
};

struct chairman_tree {
    int tot;
    tree_node tree[maxn*35];

    void ins(int lst,int &now,int l,int r,int pos) {
        now=++tot;tree[now]=tree[lst];
        tree[now].cnt++;tree[now].sum+=pos;
        if(l==r)return;
        int mid=(l+r)>>1;
        if(pos<=mid)ins(tree[lst].ls,tree[now].ls,l,mid,pos);
        else ins(tree[lst].rs,tree[now].rs,mid+1,r,pos);
    }

    int query(int x,int y,int l,int r,int pos) {
        if(r<=pos)return tree[y].sum-tree[x].sum;
        int mid=(l+r)>>1,res=tree[tree[y].ls].sum-tree[tree[x].ls].sum;
        if(pos<=mid)res=query(tree[x].ls,tree[y].ls,l,mid,pos);
        else res+=query(tree[x].rs,tree[y].rs,mid+1,r,pos);
        return res;
    }
}T;

int main() {
    n=read();
    for(int i=1;i<=n;i++) {
        a[i]=read();sum+=a[i];
    }
    for(int i=1;i<=n;i++)
        T.ins(rt[i-1],rt[i],1,sum,a[i]);
    m=read();
    for(int i=1;i<=m;i++) {
        int l=read(),r=read(),cnt=1;
        while(cnt<sum) {
            int tmp=T.query(rt[l-1],rt[r],1,sum,cnt);
            if(tmp<cnt)break; else cnt=tmp+1;//cnt就是题解里讲的num
        }
        printf("%d\n",cnt);
    }
    return 0;
}

BZOJ4408：[FJOI2016]神秘数

原文：https://www.cnblogs.com/AKMer/p/9971824.html