5255 -- 【FJOI2016】神秘数

5255 -- 【FJOI2016】神秘数

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

思路有点巧妙啊。

复杂度分析题。

显然，答案就是第一个\(i>sum[i]\)的位置，其中\(sum[i]\)表示所有权值\(\leq i\) 的元素之和。

我们考虑"暴力"。假设现在能连续组成\([1,now]\)之间的任意值，那么我们考虑有没有权值为\(now\)的元素：如果没有，答案就是\(now+1\)；否则我们的值域至少扩大了\(a_{now+1}\)（这里\(a_{now+1}\)表示所有的权值为\(now+1\)的元素和）。然后我们就将新增的值域\([now+1,now+1+a_{now+1}]\)中的所有元素加上，就这样一直迭代下去。

因为每次迭代值域至少扩大一倍，所以最多迭代\(log_2(1e9)\)次。

代码：

#include<bits/stdc++.h>
#define ll long long
#define N 100005

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

int n,m;
int rt[N];
int ls[N*50],rs[N*50];
int sum[N*50];
const int lx=1,rx=1e9;

int tot;
void Insert(int &v,int old,int lx,int rx,int p) {
    v=++tot;
    ls[v]=ls[old];
    rs[v]=rs[old];
    sum[v]=sum[old]+p;
    if(lx==rx) return ;
    int mid=lx+rx>>1;
    if(p<=mid) Insert(ls[v],ls[old],lx,mid,p);
    else Insert(rs[v],rs[old],mid+1,rx,p);
}

int query(int a,int b,int lx,int rx,int l,int r) {
    if(lx>r||rx<l) return 0;
    if(l<=lx&&rx<=r) return sum[b]-sum[a];
    int mid=lx+rx>>1;
    return query(ls[a],ls[b],lx,mid,l,r)+query(rs[a],rs[b],mid+1,rx,l,r);
}

int main() {
    n=Get();
    for(int i=1;i<=n;i++) {
        int a=Get();
        Insert(rt[i],rt[i-1],lx,rx,a);
    }
    m=Get();
    int l,r;
    while(m--) {
        l=Get(),r=Get();
        int now=0,last=0,tem;
        while(1) {
            tem=query(rt[l-1],rt[r],lx,rx,last+1,now+1);
            if(!tem) break;
            last=now+1;
            now+=tem;
        }
        cout<<now+1<<"\n";
    }
    return 0;
}

5255 -- 【FJOI2016】神秘数

原文：https://www.cnblogs.com/hchhch233/p/10458280.html