bzoj 4299 Codechef FRBSUM

定义一个集合的神秘数为不能表示成这个集合的某个子集和的最小正整数，给一个数列，多次求区间神秘数

$n \leq 100000$

sol：

考虑这个神秘数的性质，可以发现，如果神秘数是 $x$，那么 $1 \sim x$ 的所有数都能凑出来

如果每次往集合中加入一个数，如果比 $x$ 大，则神秘数不变，如果比 $x$ 小，则神秘数至少 $+x$

于是每次可以用值域主席树维护一下区间小于等于 $x$ 的所有数的和，然后对于每个区间，先把神秘数 $x$ 设为 $0$，每轮求小于等于 $x+1$ 的所有数的和，如果和就是 $x$，则 $x+1$ 是神秘数，否则继续求

可以证明这样轮次很少

#include <bits/stdc++.h>

#define LL long long

#define rep(i, s, t) for (register int i = (s), i##end = (t); i <= i##end; ++i)

#define dwn(i, s, t) for (register int i = (s), i##end = (t); i >= i##end; --i)

using namespace std;

inline int read() {

    int x = , f = ; char ch;

    for (ch = getchar(); !isdigit(ch); ch = getchar()) if (ch == '-') f = -f;

    for (; isdigit(ch); ch = getchar()) x =  * x + ch - '';

    return x * f;

}

const int maxn = , MX = 1e9;

int n, q, a[maxn];

int root[maxn], ls[maxn << ], rs[maxn << ], val[maxn << ], ToT;

void Insert(int &x, int pre, int l, int r, int pos) {

    x = ++ToT; val[x] = val[pre] + pos;

    if(l == r) return; int mid = (l + r) >> ;

    ls[x] = ls[pre]; rs[x] = rs[pre];

    if(pos <= mid) Insert(ls[x], ls[pre], l, mid, pos);

    else Insert(rs[x], rs[pre], mid+, r, pos);

}

int query(int x, int pre, int l, int r, int pos) {

    if(l == r) return val[x] - val[pre];

    int mid = (l + r) >> ;

    if(pos <= mid) return query(ls[x], ls[pre], l, mid, pos);

    else return val[ls[x]] - val[ls[pre]] + query(rs[x], rs[pre], mid+, r, pos);

}

int main() {

    n = read();

    rep(i, , n) a[i] = read(), Insert(root[i], root[i - ], , MX, a[i]);

    for(q = read(); q; q--) {

        int l = read(), r = read(); int lst = , mx = ;

        while() {

            mx = query(root[r], root[l - ], , MX, mx + );

            if(lst == mx) break; lst = mx;

            //cout << mx << " " << lst << endl;

        }

        printf("%d\n", lst + );

    }

}

巴特西

bzoj 4299 Codechef FRBSUM

最新文章

热门文章