欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[可持久化线段树] [bzoj4408] [Fjoi2016]神秘数

程序员文章站 2024-03-03 17:10:34
...

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

题解:首先考虑对于给定的一段序列如何求神秘数:
首先将序列从小到大排序,从左向右扫到i,如果a[i]>s[i-1]+1,则答案为s[i-1]+1
然后考虑如何处理询问,初始答案为1,每次算出l到r中小于等于当前答案的和s,若s<ans,则答案为ans,否则ans=s+1,这样迭代次数是O(log(sigma a[i]))的。
证明:ans’=s+1,s’=s+x*(s+1)(x为l到r中值为s+1的个数)
若x=0,则s’=s<ans’=s+1,则答案为ans’
否则,若s’>ans’,则ans”=s’+1=s+x*(s+1)+1>2*ans>2*ans
求和的过程显然可以用主席树解决

#include<cstdio>
#include<algorithm>
using namespace std;

const int MaxN=100005;

int N,M,K,Tot,Ans;
int A[MaxN],Map[MaxN],Root[MaxN];

struct Node{
    int lch,rch;
    int sum;
}Seg[MaxN*20];

#define Mid (L+R>>1)

struct QwQ{
    int id,v;
}EW[MaxN];

int Input(){
    int s=0;
    char ch;
    while(ch=getchar(),ch<'0'||ch>'9');
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-'0';
        ch=getchar();
    }
    return s;
}

bool Cmp(QwQ i,QwQ j){
    return i.v<j.v;
}

void Update(int &cur,int L,int R,int pos,int v){
    Seg[++Tot]=Seg[cur],cur=Tot;
    Seg[cur].sum+=v;
    if(L==R)
        return;
    if(Mid>=pos)
        Update(Seg[cur].lch,L,Mid,pos,v);
    else Update(Seg[cur].rch,Mid+1,R,pos,v);
}

int Binary_Search(int x){
    int l=1,r=K,mid;
    while(l<=r){
        mid=l+r>>1;
        if(Map[mid]<=x)
            l=mid+1;
        else r=mid-1;
    }
    return r;
}

int Get_Sum(int l,int r,int L,int R,int x){
    if(L==R)
        return Seg[r].sum-Seg[l].sum;
    if(x<=Mid)
        return Get_Sum(Seg[l].lch,Seg[r].lch,L,Mid,x);
    return Seg[Seg[r].lch].sum-Seg[Seg[l].lch].sum+Get_Sum(Seg[l].rch,Seg[r].rch,Mid+1,R,x);
}

int main(){
    int i,l,r,t;
    N=Input();
    for(i=1;i<=N;i++)
        EW[i].v=Input(),EW[i].id=i;
    sort(EW+1,EW+N+1,Cmp);
    for(i=1;i<=N;i++){
        A[EW[i].id]=(K+=(EW[i].v!=EW[i-1].v));
        Map[K]=EW[i].v;
    }
    for(i=1;i<=N;i++)
        Update(Root[i]=Root[i-1],1,K,A[i],Map[A[i]]);
    M=Input();
    while(M--){
        l=Input(),r=Input();
        for(Ans=1;(t=Get_Sum(Root[l-1],Root[r],1,K,Binary_Search(Ans)))>=Ans;Ans=t+1);
        printf("%d\n",Ans);
    }
    return 0;
}
相关标签: 可持久化线段树