BZOJ4299 FRBSUM <主席树>

Problem

FRBSUM

Description

数集的定义为无法用的某个子集（可以为空）的和表示的最小的非负整数。
例如，，则它的子集和中包含，，，，，，但是它无法得到。因此的为。
给定一个序列，你的任务是回答该数列的一些子区间所形成的数集的是多少。

Input

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

Ouput

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

Sample Input

Sample Output

Hint

对于的数据，, , 。

Source

By yts1999

标签：主席树

Solution

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

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

Code

#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;
}