【BZOJ4408】[FJOI2016]神秘数(主席树)
神秘 主席
2023-09-11 14:14:40 时间
【BZOJ4408】[FJOI2016]神秘数(主席树)
题面
题解
考虑只有一次询问。
我们把所有数排个序,假设当前可以表示出的最大数是\(x\)。
起始\(x=0\)。
依次考虑接下来的每个数\(a_i\),如果\(a_i\le x\),那么没有啥问题,\(x+=a_i\)。
如果\(a_i=x+1\),那么也没有问题,\(x+=a_i\)。
如果\(a_i>x\),那么\(x+1\)就拼不出来了。
那么显然考虑每次询问,首先把所有\(\le x\)的数全部加进来,然后考虑下一个比\(x\)大的数,如果其大于\(x+1\),那么直接就\(GG\)了。
否则等于\(x+1\),意味着\(x\)至少要翻一倍。
因此最多执行\(log\)次翻倍的操作。
抄起主席树暴力维护就好了。
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 100100
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
struct Node{int ls,rs,v;}t[MAX*35];int tot;
void Modify(int &x,int l,int r,int p)
{
t[++tot]=t[x];x=tot;t[x].v+=p;
if(l==r)return;int mid=(l+r)>>1;
if(p<=mid)Modify(t[x].ls,l,mid,p);
else Modify(t[x].rs,mid+1,r,p);
}
int Query(int x,int y,int l,int r,int p)
{
if(l==r)return t[x].v-t[y].v;int mid=(l+r)>>1;
if(p<=mid)return Query(t[x].ls,t[y].ls,l,mid,p);
else return Query(t[x].rs,t[y].rs,mid+1,r,p)+t[t[x].ls].v-t[t[y].ls].v;
}
int n,m,a[MAX],rt[MAX];
int main()
{
n=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=n;++i)Modify(rt[i]=rt[i-1],1,1e9,a[i]);
m=read();
while(m--)
{
int l=read(),r=read(),x=0;
while(x<1e9)
{
int v=Query(rt[r],rt[l-1],1,1e9,x+1);
if(v==x)break;x=v;
}
printf("%d\n",x+1);
}
return 0;
}
相关文章
- 神秘的 shadow-dom 浅析
- 《惢客创业日记》2018.09.16 周日 收到第一位读者的神秘来信。
- 【BZOJ4408】[Fjoi 2016]神秘数 主席树神题
- 搜索账号 排行榜客户端 Mesa——谷歌揭开跨中心超速数据仓库的神秘面纱
- 大数据背后的神秘公式(下):“贝叶斯革命”
- [转] EJB到底是什么,真的那么神秘吗??
- 排序算法系列之(三)——略显神秘的快速排序
- 起底硅谷最神秘、估值最高的大数据公司:Palantir
- 揭开SwiftUI的神秘面纱之 03 Dependency Graph 依赖图
- WWDC21 学习系列之 SwiftUI必看视频《揭开 SwiftUI 的神秘面纱》
- 硅谷亿万富翁彼得·泰尔的神秘大数据公司在新西兰遭审查
- SVD神秘值分解
- SVD神秘值分解
- 文件共享的神秘世界
- 中国神秘黑科技公开亮相,比核武器还要厉害百倍