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
1 2 4 9 10
5
1 1
1 2
1 3
1 4
1 5
Sample Output
4
8
8
8
HINT
对于100%的数据点，n,m <= 100000，∑a[i] <= 10^9
Source
福建自古出神题……
如果存在一个集合，使得$[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