Bzoj 4408: [Fjoi 2016]神秘数 可持久化线段树,神题

时间：2023-12-25 16:38:13

4408: [Fjoi 2016]神秘数

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 177  Solved: 128
[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

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

Source

鸣谢yyh上传

题解：

FJ神题！！！

这道题实在是迷幻。。。

根本想不到啊！！！QAQ！！！我一直在想数学方法。。。

看了题解，竟然是可持久化线段树！！！！(Orz 出题人)

好了不废话了。。。

先把序列从小到大排序。

假设当前神秘数为ans,则[1,ans-1]一定能用S集合中的数表示。然后如果当前加入一个数字a,则可以分为两类讨论。

1，若a<=ans,则当前可以将区间变长为：[1,ans+a-1]  ，然后神秘数变为ans+a。

2，若a>ans,则区间中有空，ans不变。

然后ans从1开始，每次求小于ans的数的和get,ans变为get+1。

这里用可持久化线段树维护即可。

 #include<bits/stdc++.h>

 using namespace std;

 #define MAXN 100010

 int sum[*MAXN],a[MAXN],root[MAXN],SIZE;

 struct node

 {

     int left,right;

 }tree[*MAXN];

 int read()

 {

     int s=,fh=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}

     while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}

     return s*fh;

 }

 void Add(int x,int &y,int l,int r,int add)

 {

     y=++SIZE;

     sum[y]=sum[x]+add;

     if(l==r)return;

     tree[y].left=tree[x].left;tree[y].right=tree[x].right;

     int mid=(l+r)/;

     if(add<=mid)Add(tree[x].left,tree[y].left,l,mid,add);

     else Add(tree[x].right,tree[y].right,mid+,r,add);

 }

 int query(int x,int y,int l,int r,int k)

 {

     if(l==r)return sum[y]-sum[x];

     int mid=(l+r)/;

     if(k<=mid)return query(tree[x].left,tree[y].left,l,mid,k);

     else return query(tree[x].right,tree[y].right,mid+,r,k)+sum[tree[y].left]-sum[tree[x].left];

 }

 int main()

 {

     int n,tot,i,m,l,r,ans,get;

     n=read();

     tot=;

     for(i=;i<=n;i++)a[i]=read(),tot+=a[i];

     SIZE=;

     for(i=;i<=n;i++)Add(root[i-],root[i],,tot,a[i]);

     m=read();

     for(i=;i<=m;i++)

     {

         l=read();r=read();

         ans=;

         while()

         {

             get=query(root[l-],root[r],,tot,ans);

             if(get<ans)break;

             ans=get+;

         }

         printf("%d\n",ans);

     }

     return ;

 }

相关文章