4408: [Fjoi 2016]神秘数
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 464 Solved: 281[][][]Description
一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13}，
1 = 12 = 1+13 = 1+1+14 = 45 = 4+16 = 4+1+17 = 4+1+1+18无法表示为集合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
福建自古出神题……
如果存在一个集合，使得$[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$，继续过程。
那么用可持久化线段树维护区间内权值范围和即可。
1 #include2 3 inline char Char(void) 4 { 5 static const int siz = 1 << 10; 6 7 static char buf[siz]; 8 static char *hd = buf + siz; 9 static char *tl = buf + siz; 10 11 if (hd == tl) 12 fread(hd = buf, 1, siz, stdin); 13 14 return *hd++; 15 } 16 17 inline int Int(void) 18 { 19 int ret = 0, neg = 0, c = Char(); 20 21 for (; c < 48; c = Char()) 22 if (c == '-')neg ^= true; 23 24 for (; c > 47; c = Char()) 25 ret = ret * 10 + c - '0'; 26 27 return neg ? -ret : ret; 28 } 29 30 const int mxn = 100005; 31 const int siz = 5000005; 32 33 int n, m, num[mxn], map[mxn], tot; 34 35 int ls[siz], rs[siz], sm[siz], cnt, root[mxn]; 36 37 void insert(int &t, int f, int l, int r, int p, int v) 38 { 39 t = ++cnt; 40 41 ls[t] = ls[f]; 42 rs[t] = rs[f]; 43 sm[t] = sm[f] + v; 44 45 if (l != r) 46 { 47 int mid = (l + r) >> 1; 48 49 if (p <= mid) 50 insert(ls[t], ls[f], l, mid, p, v); 51 else 52 insert(rs[t], rs[f], mid + 1, r, p, v); 53 } 54 } 55 56 int query(int a, int b, int l, int r, int lt, int rt) 57 { 58 if (l == lt && r == rt) 59 return sm[a] - sm[b]; 60 61 int mid = (l + r) >> 1; 62 63 if (rt <= mid) 64 return query(ls[a], ls[b], l, mid, lt, rt); 65 else if (lt > mid) 66 return query(rs[a], rs[b], mid + 1, r, lt, rt); 67 else 68 return query(ls[a], ls[b], l, mid, lt, mid) + query(rs[a], rs[b], mid + 1, r, mid + 1, rt); 69 } 70 71 signed main(void) 72 { 73 n = Int(); 74 75 for (int i = 1; i <= n; ++i) 76 num[i] = map[i] = Int(); 77 78 std::sort(map + 1, map + n + 1); 79 80 tot = std::unique(map + 1, map + n + 1) - map; 81 82 for (int i = 1; i <= n; ++i) 83 num[i] = std::lower_bound(map + 1, map + tot, num[i]) - map, 84 insert(root[i], root[i - 1], 1, tot, num[i], map[num[i]]); 85 86 m = Int(); 87 88 for (int i = 1; i <= m; ++i) 89 { 90 int l = Int(); 91 int r = Int(); 92 93 int ans = 1, get, pos; 94 95 while (true) 96 { 97 pos = std::upper_bound(map + 1, map + tot, ans) - map - 1; 98 get = query(root[r], root[l - 1], 1, tot, 1, pos); 99 if (get < ans)break;100 else ans = get + 1;101 }102 103 printf("%d\n", ans);104 }105 }
@Author: YouSiki