4408: [Fjoi 2016]神秘数

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 452 Solved: 273
[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上传

【题解】：

暴力做法：首先将这一段排序，然后如果存在某一个数，这个数比它前面的数的前缀和至少大2，那么答案就是它前面那个数的前缀和+1。
然而我们要想优化，才可AC。

　　如果我们将这段数排序，并且已知前n个数的神秘数为x，即现在凑得的数的区间为[1,x]，新加入的数为a，那么不难发现，我们凑得的数又得到了一段区间[a+1,a+x]，那么如果a+1<=x，我们就可以拼上这两段，而神秘数变为a+x+1。

　　也即是说，我们有当前解ans，我们将所有小等ans的数加起来（其实根据前面所推应该是小于，但是写小等不会错，而且对于代码来说更好些，至于为什么不多赘述），如果sigma<ans说明出现了断裂处，即此时ans为答案。否则我们将ans变为sigma+1，继续更新答案。

　　时间复杂度0（nlogn*P），其中P为常数（当数列为斐波那契时会被卡到极限40）

题解转自网络。（毕竟太弱了。QAQ）

【代码】：

#include<cstdio>
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
const int N=1e5+10,M=N*100;
int n,m,sz,ans,root[N],ls[M],rs[M],sum[M];
void insert(int &k,int last,int l,int r,int val){
    k=++sz;
    ls[k]=ls[last];
    rs[k]=rs[last];
    sum[k]=sum[last]+val;
    if(l==r) return ;
    int mid=l+r>>1;
    if(val<=mid) insert(ls[k],ls[last],l,mid,val);
    else insert(rs[k],rs[last],mid+1,r,val);
}
int query(int x,int y,int l,int r,int lim){
    int mid=l+r>>1;
    if(r<=lim) return sum[y]-sum[x];
    else if(lim<=mid) return query(ls[x],ls[y],l,mid,lim);
    else return sum[ls[y]]-sum[ls[x]]+query(rs[x],rs[y],mid+1,r,lim);
}
int main(){
    n=read();
    for(int i=1;i<=n;i++) insert(root[i],root[i-1],1,1e9,read()); 
    m=read();
    for(int i=1,l,r;i<=m;i++){
        l=read();r=read();ans=1;
        for(int sigma;(sigma=query(root[l-1],root[r],1,1e9,ans))>=ans;ans=sigma+1);
        printf("%d
",ans);
    }
    return 0;
}