BZOJ 4299 Codechef FRBSUM - NekoMio's Blog

Description#

数集S的ForbiddenSum定义为无法用S的某个子集（可以为空）的和表示的最小的非负整数。例如，S={1,1,3,7}，则它的子集和中包含0(S’=∅)，1(S’={1})，2(S’={1,1})，3(S’={3})，4(S’={1,3})，5(S’ = {1, 1, 3})，但是它无法得到6。因此S的ForbiddenSum为6。给定一个序列A，你的任务是回答该数列的一些子区间所形成的数集的ForbiddenSum是多少。

Input#

输入数据的第一行包含一个整数N，表示序列的长度。接下来一行包含N个数，表示给定的序列A（从1标号）。接下来一行包含一个整数M，表示询问的组数。接下来M行，每行一对整数，表示一组询问。

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%的数据，1≤N,M≤100000,1≤A_i≤10^9，1≤A_1+A_2+…+A_N≤10^9。

题解#

可以看出

如果一个区间能组出1~n的数而且有一个数小于等于n+1
则这个区间一定能构造出 n+1

然后就可以了

用主席树维护一下就可以了

复习一下主席树

1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
const int INF = 1e9;
6
struct Seg_Node
7
{
8
    int l, r;
9
    Seg_Node *ch[2];
10
    int Sum;
11
} * root[100005], *null;
12
int a[100005];
13
Seg_Node *NewSeg_Node()
14
{
15
    Seg_Node *S = new Seg_Node();
16
    S->ch[0] = S->ch[1] = null;
17
    return S;
18
}
19
void copy(Seg_Node *&a, Seg_Node *b)
20
{
21
    if (b == null)
22
        a = null;
23
    else
24
        a = NewSeg_Node(), *a = *b;
25
}
26
void Update(int v, int l, int r, Seg_Node *&rt1, Seg_Node *rt2)
27
{
28
    copy(rt1, rt2);
29
    if(rt1==null)
30
        rt1=NewSeg_Node();
31
    rt1->Sum += v;
32
    rt1->l = l, rt1->r = r;
33
    if (l == r)
34
        return;
35
    int m = l + r >> 1;
36
    if (v <= m)
37
    {
38
        Update(v, l, m, rt1->ch[0], rt2->ch[0]);
39
    }
40
    else
41
    {
42
        Update(v, m + 1, r, rt1->ch[1], rt2->ch[1]);
43
    }
44
}
45
int Query(int R, int l, int r, Seg_Node *rt1, Seg_Node *rt2)
46
{
47
    if (R >= r)
48
        return rt1->Sum - rt2->Sum;
49
    int m = l + r >> 1;
50
    if (R <= m)
51
        return Query(R, l, m, rt1->ch[0], rt2->ch[0]);
52
    return Query(R, l, m, rt1->ch[0], rt2->ch[0]) + Query(R, m + 1, r, rt1->ch[1], rt2->ch[1]);
53
}
54
int main()
55
{
56
    null = new Seg_Node();
57
    null->ch[0] = null->ch[1] = null;
58
    root[0] = null;
59
    int n;
60
    scanf("%d", &n);
61
    for (int i = 1; i <= n; i++)
62
        scanf("%d", &a[i]);
63
    for (int i = 1; i <= n; i++)
64
    {
65
        Update(a[i], 1, 1e9, root[i], root[i - 1]);
66
    }
67
    int m;
68
    scanf("%d", &m);
69
    int a, b, ans;
70
    while (m--)
71
    {
72
        scanf("%d%d", &a, &b);
73
        int res = 1;
74
        ans = min(INF, Query(res, 1, 1e9, root[b], root[a - 1]));
75
        while (ans >= res && res < 1e9)
76
        {
77
            res = ans + 1;
78
            ans = min(INF, Query(res, 1, 1e9, root[b], root[a - 1]));
79
        }
80
        printf("%d\n", ans + 1);
81
    }
82
}