文档章节

BZOJ4408 - [FJOI2016]神秘数

o
 osc_z1hvg4cu
发布于 2018/04/24 21:26
字数 673
阅读 20
收藏 0

精选30+云产品,助力企业轻松上云!>>>

Portal

##Description 一个可重复数字集合$S$的神秘数定义为最小的不能被$S$的子集的和表示的正整数。现给出一个$n(n\leq10^5)$个数的数列${a_n}(\Sigma a_i\leq10^9)$和$m(m\leq10^5)$次询问,每次给出两个数$L,R$,求集合${a_{L..R}}$的神秘数。

##Solution 可持久化线段树。 首先考虑如何求出集合的神秘数。定义$t$和$ans$,表示用不超过$t$的元素能够凑成$[1,ans-1]$中的所有数。初始时有$t=0,ans=1$。接下来考虑加上一个数$x$后对$ans$有何影响。若$x>ans$则依然无法凑出$ans$,不变;否则能够凑出$[1,ans+x-1]$中的所有数,$ans=ans+x$。那么求出$[t+1,ans]$中所有元素的和,加到$ans$上就得到了新的$ans$,新的$t$等于原$ans$。简化一下过程:初始$ans=1$,每次令$ans$等于$[1,ans]$中所有元素的和$+1$,直到$ans$不再增大为止。由于$ans$每次如果增大则至少增大$t+1$,所以最多进行$log$次。 那么建立$n$棵权值线段树分别记录前若干个数中的权值分布情况,询问区间$[L,R]$时用线段树$R$减线段树$L-1$即可。

时间复杂度$O(mlog^2n)$。

##Code

//[FJOI2016]神秘数
#include <cstdio>
typedef long long lint;
inline char gc()
{
    static char now[1<<16],*s,*t;
    if(s==t) {t=(s=now)+fread(now,1,1<<16,stdin); if(s==t) return EOF;}
    return *s++;
}
inline int read()
{
    int x=0; char ch=gc();
    while(ch<'0'||'9'<ch) ch=gc();
    while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();
    return x;
}
const int N=1e5+10;
int n,m;
int cnt,rt[N];
struct node{int chL,chR; lint sum;} nd[N*32];
void update(int p) {nd[p].sum=nd[nd[p].chL].sum+nd[nd[p].chR].sum;}
void ins(int &p,int L0,int R0,int x)
{
    nd[++cnt]=nd[p]; p=cnt;
    if(L0==R0) {nd[p].sum+=x; return;}
    int mid=L0+R0>>1;
    if(x<=mid) ins(nd[p].chL,L0,mid,x);
    else ins(nd[p].chR,mid+1,R0,x);
    update(p);
}
lint optL,optR; lint qres;
void query(int p1,int p2,int L0,int R0)
{
    if(p1==p2) return;
    if(optL<=L0&&R0<=optR) {qres+=nd[p2].sum-nd[p1].sum; return;}
    int mid=L0+R0>>1;
    if(optL<=mid) query(nd[p1].chL,nd[p2].chL,L0,mid);
    if(mid<optR) query(nd[p1].chR,nd[p2].chR,mid+1,R0);
}
int main()
{
    n=read(); int maxA=1e9;
    for(int i=1;i<=n;i++)
        ins(rt[i]=rt[i-1],1,maxA,read());
    m=read();
    for(int i=1;i<=m;i++)
    {
        int L=read(),R=read();
        lint ans=1;
        while(true)
        {
            optL=1,optR=ans,qres=0,query(rt[L-1],rt[R],1,maxA);
            if(qres<ans) break; else ans=qres+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

##P.S. 我又开始懒得写题解了... 本来我想权值$10^9<2^{30}$所以线段树只开了$30N$个节点,但事实上应该开$31N$ 0(xp )~

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

渗透测试的概念和实战

目录 1. 前言 2. 常见web安全漏洞 3. 思路 3.1渗透测试思路 3.2黑客攻击思路 4. 暴力破解 4.1谷歌黑语法 4.1.1 黑语法inurl:搜索url包含指定字符串 4.1.2 黑语法intitle:搜索网页中的标题名...

六道木
40分钟前
19
0
Nginx搭建

Web服务器 放置网站文件,全世界浏览 可以放置数据文件,让全世界可以下载。 Nginx官方网站www.nginx.org #rz nginx-1.11.6.tar.gz #ls #rpm -q zlib-devel pcre-devel #yum –y install zli...

osc_fnto2dbd
51分钟前
14
0
如何在1分钟内CSDN收益1000万,走上人生巅峰?!

事情的起因源于前几日CSDN专栏作者群中有位同志自曝收益:426584.46元(不用数了42万+,未证实是否属实),瞬间刷屏。 那么作为一位普通的技术分享者,是否有机会利用开源项目短时间内赢取白...

osc_8db3mwb5
52分钟前
23
0
【java基础(五十)】为什么要使用泛型程序设计

从Java程序设计语言1.0版发布以来,变化最大的部分就是泛型。致使Java SE 5.0中增加泛型机制的主要原因是为了满足1999年制定的最早的Java规范需求之一(JSR 14)。专家组花费了5年左右的时间...

osc_qcm2mqmy
54分钟前
20
0
如何将Unix时间戳转换为DateTime,反之亦然? - How can I convert a Unix timestamp to DateTime and vice versa?

问题: There is this example code, but then it starts talking about millisecond / nanosecond problems. 有此示例代码,但随后开始谈论毫秒/纳秒问题。 The same question is on MSDN, ......

javail
54分钟前
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部