BZOJ4299: Codechef FRBSUM(主席树)

题意

数集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是多少。

Sol

若序列已经被从小到大排序

考虑当前位置为$i$，且$[1, s_i]$内的数都可以被拼成

那么若$a[i + 1] > s_i + 1$，那么$a[i + 1]$不能被拼成

于是我们可以这样去做

首先在集合内找比$s = 1$小的数的和(也就相当于上面的前缀和)，若比$1$少，则答案为$1$

若询问得到的结果是$1$，则$s = 1 + 1 = 2$，此时我们去找比$2$小的和

若$< 2$，则答案为$2$，不断做下去，直到不符合条件为止。

不符合条件，实际上也就是$a[i + 1] > s_i + 1$

每次在一段区间内询问小于等于某一个数的和，可以用主席树维护，

时间复杂度：若一直是符合条件的，我们每次询问会至少让si翻一倍，因此单次询问的复杂度为log sn，

加上主席树的复杂度，总复杂度为$O(Q logn log sn)$

#include<iostream>

#include<cstdio>

using namespace std;

const int MAXN =  * 1e6 + ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N, a[MAXN], lim;

int ls[MAXN], rs[MAXN], sum[MAXN], tot, root[MAXN];

void insert(int &k, int p, int l, int r, int pos) {

    k = ++ tot;

    ls[k] = ls[p]; rs[k] = rs[p]; sum[k] = sum[p] + pos;

    if(l == r) return ;

    int mid = l + r >> ;

    if(pos <= mid) insert(ls[k], ls[p], l, mid, pos);

    else insert(rs[k], rs[p], mid + , r, pos);

}

int Query(int k, int p, int l, int r, int val) {

    if(l > val) return ;

    if(r <= val) return sum[k] - sum[p];

    int mid = l + r >> ;

    int suml = sum[ls[k]] - sum[ls[p]];

    if(val > mid) return suml + Query(rs[k], rs[p], mid + , r, val);

    else return Query(ls[k], ls[p], l, mid, val);

}

int solve(int l, int r) {

    int nxt = ;

    for(int i = ; ; i = nxt + ) {

        nxt = Query(root[r], root[l - ], , lim, i);//询问区间内<=i的数的和

        if(nxt < i) return i;

    }

}

int main() {

    N = read();

    for(int i = ; i <= N; i++) a[i] = read(), lim = max(a[i], lim);

    for(int i = ; i <= N; i++) insert(root[i], root[i - ], , lim, a[i]);

    int Q = read();

    while(Q--) {

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

        printf("%d\n", solve(l, r));

    }

    return ;

}

巴特西

BZOJ4299: Codechef FRBSUM(主席树)

题意

Sol

最新文章

热门文章