bzoj 4408 [Fjoi 2016]神秘数

bzoj 4408 [Fjoi 2016]神秘数

​​ 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​​，求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。

Input 第一行一个整数n，表示数字个数。 第二行n个整数，从1编号。 第三行一个整数m，表示询问个数。 以下m行，每行一对整数l,r，表示一个询问。

Output 对于每个询问，输出一行对应的答案。

Sample Input 5

1 2 4 9 10

5

1 1

1 2

1 3

1 4

1 5

Sample Output 2

4

8

8

8

HINT 对于100%的数据点，n,m <= 100000，∑a[i] <= 10^9

我以权值建立主席树 然后每个点一个根

然后每次认为我的答案先是1 然后查询一下比我当前答案小的数的和是多少 如果查询的值大于我当前假设的答案 那么答案至少可以是当前查询到的和 然后 我假设我的ans是这个和+1 直到这个和小于我假定的答案 那么我这个答案就是我无法做到的了

#include#include#define N 110000using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}struct node{ int left,right,v;}tree[40*N];int n,num,w[N],root[N],m;inline void update(int x){ tree[x].v=tree[tree[x].left].v+tree[tree[x].right].v;}inline void insert1(int &x,int l,int r,int v){ tree[++num]=tree[x];x=num; if (l==r) {tree[x].v+=v;return;}int mid=l+r>>1; if (v<=mid) insert1(tree[x].left,l,mid,v);else insert1(tree[x].right,mid+1,r,v);update(x);}inline long long query(int rt1,int rt2,int l,int r,int l1,int r1){ if (l1<=l&&r1>=r) return tree[rt2].v-tree[rt1].v; int mid=l+r>>1;int tmp=0; if (l1<=mid) tmp+=query(tree[rt1].left,tree[rt2].left,l,mid,l1,r1); if (r1>mid) tmp+=query(tree[rt1].right,tree[rt2].right,mid+1,r,l1,r1);return tmp;}int main(){ freopen("bzoj4408.in","r",stdin); n=read();int M=0; for (int i=1;i<=n;++i) w[i]=read(),M=max(w[i],M); for (int i=1;i<=n;++i) root[i]=root[i-1],insert1(root[i],1,M,w[i]);m=read(); for (int i=1;i<=m;++i){ int l=read(),r=read();int ans=1;int tmp=0; for (ans;;ans=tmp+1){ tmp=query(root[l-1],root[r],1,M,1,ans); if (tmp

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。