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

时间：2023-11-28 12:12:32

4408: [Fjoi 2016]神秘数

题目连接：

http://www.lydsy.com/JudgeOnline/problem.php?id=4408

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

题意

题解：

权限题

用持久化线段树去维护就好了

假设我当前的答案是ans,那么如果在这个区间小于等于ans的数的和sum小于了ans，那么显然是不能构成ans的，那就直接输出就好了

否则就更新ans=sum+1，然后这样不停的迭代下去就好了。

这个解释的话，用dp去想就好了

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+7;

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;

}

struct node

{

    int l,r,sum;

}T[maxn*100];

int n,cnt,a[maxn],root[maxn],m,l,r,ans,tot;

void update(int l,int r,int &x,int y,int val)

{

    T[++cnt]=T[y],T[cnt].sum+=val;x=cnt;

    if(l==r)return;

    int mid=(l+r)/2;

    if(val<=mid)update(l,mid,T[x].l,T[x].l,val);

    else update(mid+1,r,T[x].r,T[x].r,val);

}

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

{

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

    int mid=(l+r)/2;

    if(pos<=mid)return query(l,mid,T[x].l,T[y].l,pos);

    else return query(mid+1,r,T[x].r,T[y].r,pos)+T[T[y].l].sum-T[T[x].l].sum;

}

int main()

{

    n=read();

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

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

    for(m=read();m;m--)

    {

        l=read(),r=read(),ans=1;

        while(1)

        {

            int tmp=query(1,tot,root[l-1],root[r],ans);

            if(tmp<ans)break;

            ans=tmp+1;

        }

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

    }

}

相关文章