BZOJ4299 FRBSUM <主席树>

Posted on Symbols count in article: 751 Reading time ≈ 3 mins.

Problem

FRBSUM

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

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

Input

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

Ouput

对于每组询问，输出一行表示对应的答案。

Sample Input

1
2
3
4
5
6
7
8
5
1 2 4 9 10
5
1 1
1 2
1 3
1 4
1 5

Sample Output

1
2
3
4
5
2
4
8
8
8

Hint

对于100%100\%的数据，1≤N,M≤1051\le N,M\le10^5, 1≤Ai≤1091\le A_i\le10^9, 1≤A1+A2+⋯+AN≤1091\le A_1+A_2+\cdots+A_N\le10^9。

Source

By yts1999

标签：主席树

Solution

本题和【FJOI2016】神秘数相同，双倍经验。

首先不难发现一个结论，若某集合当前能凑出0∼mx0\sim mx中的所有数，加入一个数xx，可凑出的数的值域扩展当且仅当x≤mx+1x\le mx+1，并且会将值域扩展到0∼mx+x0\sim mx+x。
如此，对于每个区间[l,r][l,r]，从小到大逐一将每个数加入到集合中，像上面那样不断扩展值域，如果加入某个数时x>mx+1x>mx+1，值域无法继续扩充，那么mx+1mx+1即为最小的不能凑成的数。
这个过程可以用一棵值域主席树维护，每次将所有小于等于mx+1mx+1的数求和，作为新的mxmx，若mxmx在某次这样的操作中不变，则无法继续扩展，输出答案mx+1mx+1。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define MAX_N 100000
#define INF 1000000000
#define mid ((s+t)>>1)
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, rt[MAX_N+5], cnt;
struct node {int ls, rs, s;} tr[MAX_N*32];
void modify(int v, int o, int s, int t, int p) {
    tr[v] = tr[o], tr[v].s += p;	if (s == t) return;
    if (p <= mid) modify(tr[v].ls = ++cnt, tr[o].ls, s, mid, p);
    else modify(tr[v].rs = ++cnt, tr[o].rs, mid+1, t, p);
}
int query(int l, int r, int s, int t, int p) {
    if (s == t) return tr[r].s-tr[l].s;
    int lsum = tr[tr[r].ls].s-tr[tr[l].ls].s;
    if (p <= mid) return query(tr[l].ls, tr[r].ls, s, mid, p);
    return lsum+query(tr[l].rs, tr[r].rs, mid+1, t, p);
}
int main() {
    read(n);
    for (int i = 1, x; i <= n; i++)
        read(x), modify(rt[i] = ++cnt, rt[i-1], 1, INF, x);
    read(m);
    while (m--) {
        int l, r;	read(l), read(r);
        for (int mx = 0, lst = 0; ; lst = mx) {
            mx = query(rt[l-1], rt[r], 1, INF, mx+1);
            if (mx == lst) {printf("%d\n", mx+1); break;}
        }
    }
    return 0;
}