2020牛客NOIP赛前集训营-提高组（第一场） C题 题解

本场全部题解见此

更好的阅读体验

C 牛牛的凑数游戏

题意简述

对于一个多重数集 ，对于一非负整数 ，若存在 且 中所有数字之和恰好等于 ，则说 可以表示 。

给定一个序列，多次询问一个给定的区间中的数构成的多重数集最小的不能表示出的数。

算法标签

题目性质发掘 主席树/树状数组

算法分析

我们发现直接处理多重数集很难，因此考虑其等价条件。

引理： 将一个多重数集升序排序，记为 ，求 的前缀和为 ，则第一个满足 的位置对应的数，即 为这个多重数集不能表示出的最小的数。

证明：

充分性显然， 只有可能由小于它的数的加和表示，因此仅可以使用 ，而将这些数都加起来都表示不了 ，因此无法表示。

再证必要性，我们只需要证明比 小的数都能被表示出来即可。

考虑归纳证明，显然 时 无法被表示出，因此下设 ，此时 能被表示出。

对 ,假设比 小的数都能被表示出来，下面证明比 小的数能表示出来。

因为 ，所以 ，对 分两类讨论：

1. 由归纳知可以被表示出；
2. 则 ，因此 可以被表示为前 个数的和减去前 个数中部分数的和，因此一定可以被表示出。

这里可能用图解释更为直观：

由此归纳证明。

因此我们只需要对询问区间的数升序排序并判断即可，这样有 分。

考虑优化上面的算法。我们发现对于当前的排序后前缀和 ，**所有未加入前缀和且 的数都不可能使 成立**，因此可以直接加到 中不必再判断。

这个过程 基本是倍增的，因此操作次数不超过 次。

现在问题转化为对给定的区间求一个值域范围内的数的和。

这个问题可以直接在线+主席树搞掉，代码量不算很大。

离线算法可以用莫队+动态开点线段树，时间复杂度大概是 ，好像容易被卡。

当然我们也可以考虑离线+树状数组。

我们发现对于一个给定的 ，它询问的的值域范围的最大值是不断增大的，因此可以离线不断加入 ，这个过程可以用树状数组实现。

其实这个树状数组的过程与整体二分求区间第 大的数中的树状数组过程是类似的

有关这种树状数组的使用，可以看一看这一道题目： HDU4417

主席树/树状数组实现的时间复杂度 。

代码实现

订正是写的是主席树。

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
#define maxm 20000005
#define inf 0x3f3f3f3f
#define int long long
#define mod 1000000007
#define local
void file(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
template <typename Tp>void read(Tp &x){
    x=0;int fh=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-'){fh=-1;}c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=fh;
}
int n,m;
int a[maxn];
#define mid ((l+r)>>1)
int st[maxm],lson[maxm],rson[maxm],tot,T[maxn];
void pushup(int x){st[x]=st[lson[x]]+st[rson[x]];}
int upd(int x,int l,int r,int p,int v){//主席树单点修改
    int rt=++tot;
    st[rt]=st[x];lson[rt]=lson[x];rson[rt]=rson[x];
    if(l==r){
        st[rt]+=v;
        return rt;
    }
    if(p<=mid)lson[rt]=upd(lson[x],l,mid,p,v);
    else rson[rt]=upd(rson[x],mid+1,r,p,v);
    pushup(rt);
    return rt;
}
int query(int p,int q,int l,int r,int L,int R){//主席树区间查询
    if(l>R||r<L)return 0;
    if(l>=L&&r<=R)return st[q]-st[p];
    return query(lson[p],lson[q],l,mid,L,R)+query(rson[p],rson[q],mid+1,r,L,R); 
}
int calc(int l,int r){
    int tsm=0,pl=0,pr=0;//pl表示当前已经用到的 a 的最大值，pr表示前缀和
    while(1){           //上面代码注释可能需要感性理解
        tsm=query(T[l-1],T[r],1,100000000000000ll,pl+1,pr+1);
        if(!tsm)return pr+1;
        pl=pr+1;pr+=tsm;
    }
    return pr+1;
}
signed main(){
    read(n);read(m);
    for(int i=1;i<=n;++i)read(a[i]);
    for(int i=1;i<=n;++i)T[i]=upd(T[i-1],1,100000000000000ll,a[i],a[i]);//主席树基本操作
    for(int i=1,l,r;i<=m;++i){
        read(l);read(r);
        printf("%lld\n",calc(l,r));
    }
    return 0;
}