首页 > 代码库 > 【BZOJ-4408】神秘数 可持久化线段树
【BZOJ-4408】神秘数 可持久化线段树
4408: [Fjoi 2016]神秘数
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 475 Solved: 287
[Submit][Status][Discuss]
Description
一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13}，
1 = 1
2 = 1+1
3 = 1+1+1
4 = 4
5 = 4+1
6 = 4+1+1
7 = 4+1+1+1
8无法表示为集合S的子集的和，故集合S的神秘数为8。
现给定n个正整数a[1]..a[n]，m个询问，每次询问给定一个区间[l,r](l<=r)，求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。
Input
第一行一个整数n，表示数字个数。
第二行n个整数，从1编号。
第三行一个整数m，表示询问个数。
以下m行，每行一对整数l,r，表示一个询问。
Output
对于每个询问，输出一行对应的答案。
Sample Input
1 2 4 9 10
5
1 1
1 2
1 3
1 4
1 5
Sample Output
4
8
8
8
HINT
对于100%的数据点，n,m <= 100000，∑a[i] <= 10^9
Source
鸣谢yyh上传
Solution
这道题挺好的思路。
首先考虑在集合中已经选出$k$个数的时候，再加入第$k+1$个数的情况。
显然有当$a_{k+1}>\sum ^{k}_{i=1} a_{k} +1$时，$ans=\sum ^{k}_{i=1} a_{k}+1$
否则显然这个这些数能组合出的范围扩大$a_{k+1}$
所以思路就是对于一个$ans$，求出$\sum ^{R}_{i=L} (a_{i}<ans) a_{i}$，如果这些数能组合到$ans$，那么这个$ans$只能扩大，所以把$ans$扩大到$\sum ^{R}_{i=L} (a_{i}<ans) a_{i} +1$继续做，否则得到神秘数。
所以支持这样做的还是利用可持久化线段树求出。
但是这样的复杂度还是比较暴力的，不过题目中说了$\sum a_{i}<10^{9}$所以复杂度最坏是 $O(MlogNlog10^{9})$
话说这题被xyx秒了....
Code
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>using namespace std;inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();} while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} return x*f;}#define MAXN 100010int N,M,a[MAXN];namespace PrTree{ int root[MAXN],sum[MAXN*20],lson[MAXN*20],rson[MAXN*20],sz; inline void Insert(int l,int r,int &x,int last,int pos,int val) { x=++sz; lson[x]=lson[last],rson[x]=rson[last]; sum[x]=sum[last]+val; if (l==r) return; int mid=(l+r)>>1; if (pos<=mid) Insert(l,mid,lson[x],lson[last],pos,val); else Insert(mid+1,r,rson[x],rson[last],pos,val); } inline int Query(int l,int r,int L,int R,int x,int y) { if (L>R) return 0; if (L<=l && R>=r) return sum[y]-sum[x]; int mid=(l+r)>>1,re=0; if (L<=mid) re+=Query(l,mid,L,R,lson[x],lson[y]); if (R>mid) re+=Query(mid+1,r,L,R,rson[x],rson[y]); return re; }}using namespace PrTree;int ls[MAXN];int main(){ N=read(); for (int i=1; i<=N; i++) ls[i]=a[i]=read(); sort(ls+1,ls+N+1); int tot=unique(ls+1,ls+N+1)-ls-1; for (int i=1; i<=N; i++) a[i]=lower_bound(ls+1,ls+tot+1,a[i])-ls; for (int i=1; i<=N; i++) PrTree::Insert(1,tot,root[i],root[i-1],a[i],ls[a[i]]); M=read(); while (M--) { int l=read(),r=read(); int ans=1,up,pos; while (1) { pos=upper_bound(ls+1,ls+tot+1,ans)-ls-1; if (ans<=(up=PrTree::Query(1,tot,1,pos,root[l-1],root[r]))) ans=up+1; else break; } printf("%d\n",ans); } return 0;}
【BZOJ-4408】神秘数 可持久化线段树