【Codechef FRBSUM】【FJOI2016】【BZOJ4299】【BZOJ 4408】可持久化线段树

4408: [Fjoi 2016]神秘数

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

Solution

这题的思路还是很妙的。

我们假设前面选的数能取到的最大值为k，即[1,k]中的所有数都能取到，现在加入了一个数x。

若x <= k+1，则能取到的最大值为k+x，神秘数为k+x+1

若x > k+1，则能取到的最大值仍为k，神秘数为k+1

对于一个询问(l,r)，设当前神秘数为k，若Σai >= k（ai <= k && i∈[l,r]），则说明k仍能增大，否则，神秘数即为k。

而求前缀和，可以用可持久化线段树来解决。

每次寻找，k至少增加一倍，每次求前缀和是logn，总的时间复杂度是O(Q*log1e9²)

Code

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <string>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 #define REP(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
10 typedef long long LL;
11 const int maxn = 1e5+10;
12 int n, a[maxn];
13 struct Node
14 {
15     LL sum; int ls, rs;
16     Node() { sum = ls = rs = 0; }
17 }t[maxn*50];
18 int rt[maxn], t_cnt, mx_a;
19 
20 void pushup(Node &x) { x.sum = t[x.ls].sum+t[x.rs].sum; }
21 
22 void update(int now_rt, int las_rt, int l, int r, int x)
23 {
24     if (l == r)
25     {
26         t[now_rt].sum = t[las_rt].sum+x;
27         return ;
28     }
29     int mid = (l+r)>>1;
30     if (x <= mid)
31     {
32         t[now_rt].rs = t[las_rt].rs, t[now_rt].ls = ++t_cnt;
33         update(t[now_rt].ls, t[las_rt].ls, l, mid, x);
34     }
35     else
36     {
37         t[now_rt].ls = t[las_rt].ls, t[now_rt].rs = ++t_cnt;
38         update(t[now_rt].rs, t[las_rt].rs, mid+1, r, x);
39     }
40     pushup(t[now_rt]);
41 }
42 
43 int query(int rt_1, int rt_2, int l, int r, int x)
44 {
45     if (l > x) return 0;
46     if (r <= x) return t[rt_2].sum-t[rt_1].sum;
47     int mid = (l+r)>>1;
48     int ret = query(t[rt_1].ls, t[rt_2].ls, l, mid, x);
49     if (x > mid) ret += query(t[rt_1].rs, t[rt_2].rs, mid+1, r, x);
50     return ret;
51 }
52 
53 int calc(int l, int r)
54 {
55     int ret = 1, temp = 0;
56     while ((temp = query(rt[l-1], rt[r], 1, mx_a, ret)) >= ret) ret = temp+1;
57     return ret;
58 }
59 
60 int main()
61 {
62     scanf("%d", &n);
63     REP(i, 1, n) scanf("%d", &a[i]), mx_a = max(mx_a, a[i]);
64     REP(i, 1, n) update(rt[i] = ++t_cnt, rt[i-1], 1, mx_a, a[i]);
65     int Q, l, r;
66     scanf("%d", &Q);
67     while (Q --)
68     {
69         scanf("%d %d", &l, &r);
70         printf("%d
", calc(l, r));
71     }
72     return 0;
73 }

View Code