4408: [Fjoi 2016]神秘数

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

[Submit][Status][Discuss]

福建自古出神题……

如果存在一个集合,使得$[1,x]$内的数字都能被表示,新加入一个数$y$,那么会出现如下两种情况:

  1. $y \leq x+1$,则新集合可以表示$[1,x+y]$内的所有数字。

  2. $y \gt x+1$,则新集合表示的区间会产生“断裂”,即$x+1$依旧无法被表示,所以该集合的神秘数还是$x+1$。

基于以上分析,产生下面的算法,用以求一个给定集合的神秘数:

首先设$ans=1$,作为最初假象的神秘数,然后求出

\[get=\sum_{a_{i} \leq ans}a_{i}\]

那么如果$get \lt ans$,则$ans$就是神秘数,否则令$ans=get+1$,继续过程。

那么用可持久化线段树维护区间内权值范围和即可。

 #include <bits/stdc++.h>

 inline char Char(void)
{
static const int siz = << ; static char buf[siz];
static char *hd = buf + siz;
static char *tl = buf + siz; if (hd == tl)
fread(hd = buf, , siz, stdin); return *hd++;
} inline int Int(void)
{
int ret = , neg = , c = Char(); for (; c < ; c = Char())
if (c == '-')neg ^= true; for (; c > ; c = Char())
ret = ret * + c - ''; return neg ? -ret : ret;
} const int mxn = ;
const int siz = ; int n, m, num[mxn], map[mxn], tot; int ls[siz], rs[siz], sm[siz], cnt, root[mxn]; void insert(int &t, int f, int l, int r, int p, int v)
{
t = ++cnt; ls[t] = ls[f];
rs[t] = rs[f];
sm[t] = sm[f] + v; if (l != r)
{
int mid = (l + r) >> ; if (p <= mid)
insert(ls[t], ls[f], l, mid, p, v);
else
insert(rs[t], rs[f], mid + , r, p, v);
}
} int query(int a, int b, int l, int r, int lt, int rt)
{
if (l == lt && r == rt)
return sm[a] - sm[b]; int mid = (l + r) >> ; if (rt <= mid)
return query(ls[a], ls[b], l, mid, lt, rt);
else if (lt > mid)
return query(rs[a], rs[b], mid + , r, lt, rt);
else
return query(ls[a], ls[b], l, mid, lt, mid) + query(rs[a], rs[b], mid + , r, mid + , rt);
} signed main(void)
{
n = Int(); for (int i = ; i <= n; ++i)
num[i] = map[i] = Int(); std::sort(map + , map + n + ); tot = std::unique(map + , map + n + ) - map; for (int i = ; i <= n; ++i)
num[i] = std::lower_bound(map + , map + tot, num[i]) - map,
insert(root[i], root[i - ], , tot, num[i], map[num[i]]); m = Int(); for (int i = ; i <= m; ++i)
{
int l = Int();
int r = Int(); int ans = , get, pos; while (true)
{
pos = std::upper_bound(map + , map + tot, ans) - map - ;
get = query(root[r], root[l - ], , tot, , pos);
if (get < ans)break;
else ans = get + ;
} printf("%d\n", ans);
}
}

@Author: YouSiki

05-04 01:48