FJOI2016 神秘数

偏执的太偏执、 2021-09-29 08:02 241阅读 0赞

题目大意

给定长为$N$一个序列，每次询问一个区间，求最小的不能表示为由区间内若干个（可以是$0$个）数的和的非负整数。

考虑一个可重集合$S$，设抽取$S$中若干个数相加无法得到的最小非负整数为$Ans\_S$

显然$Ans\_\{\\emptyset\}=1$

当加入一个元素$x$时

当$x>Ans\_S$时，原先的$Ans\_S$仍然无法凑出来，所以答案不变

当$x\\leq Ans\_S$时，原先的$0,1...Ans\_S-1$可表示为$x,x+1...Ans\_S-1+x$由于$x\\leq Ans\_S-1$

所以$S$加入$x$后得到的$K$一可以表示$0,1...Ans\_S+x-1$，而$Ans\_S+x$仍然无法凑出来

所以$Ans\_K=Ans\_S+x$

但是这样直接做还是会$TLE$，因为每次询问得把区间扫一遍。

我们想一个很暴力的优化。

设当前答案为$ans$，你已经加上了区间内小于等于$last$的数的和。

由于答案已经达到了$ans$，我们求出$sum=$区间内满足$last<x\\leq ans$的所有$x$的和。

若$sum=0$，则答案已经不再影响，直接停止就好，否则我们令$last=ans，ans=ans+sum$即可。

初始时$last=0,ans=1$。

这看起来很暴力，但是其中对于所有的若$sum>0$，则一定有$sum>last$，所以每两次操作$last$至少扩大一倍，而所有数的总和又是固定的，所以对于每一次询问$ans$只会进行$\\log$级别次数的增加。

区间求一定值域内的和，用可持久化线段树维护即可。

复杂度$O(N\\log(\\sum A\_i)+M\\log^2(\\sum A\_i))$

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #define LL long long
    #define M 120000
    #define mid ((l+r)>>1)
    #define MAXN 1000000002
    using namespace std;
    int read(){
    	int nm=0,fh=1; char cw=getchar();
    	for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;
    	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
    	return nm*fh;
    }
    int n,m,sum[M*32],L[M*32],R[M*32],rt[M],cnt;
    void write(int x){if(x>9) write(x/10); putchar(x-(x/10)*10+'0');}
    void ins(int &x,int pre,int l,int r,int pos){
    	x=++cnt,L[x]=L[pre],R[x]=R[pre];
    	sum[x]=sum[pre]+pos; if(l==r) return;
    	if(pos<=mid) ins(L[x],L[pre],l,mid,pos);
    	else ins(R[x],R[pre],mid+1,r,pos);
    }
    int qry(int now,int pre,int l,int r,int ls,int rs){
    	if(sum[now]==sum[pre]||r<ls||rs<l) return 0;
    	if(ls<=l&&r<=rs) return sum[now]-sum[pre];
    	return qry(L[now],L[pre],l,mid,ls,rs)+qry(R[now],R[pre],mid+1,r,ls,rs);
    }
    int main(){
    	n=read();
    	for(int i=1;i<=n;i++) m=read(),ins(rt[i],rt[i-1],1,MAXN,m);
    	for(int T=read(),last=0,ans=1;T;T--,last=0,ans=1){
    		int ls=read()-1,rs=read(),now=0;
    		while(true){
    			now=qry(rt[rs],rt[ls],1,MAXN,last+1,ans);
    			if(!now) break; last=ans,ans+=now;
    		} write(ans),putchar('\n');
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/OYJason/p/9743208.html