欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ4299: Codechef FRBSUM(主席树)

程序员文章站 2024-01-12 08:15:40
题意 题目链接 数集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}), ......

题意

题目链接

数集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 = 3 * 1e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', 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 >> 1;
    if(pos <= mid) insert(ls[k], ls[p], l, mid, pos);
    else insert(rs[k], rs[p], mid + 1, r, pos);
}
int query(int k, int p, int l, int r, int val) {
    if(l > val) return 0;
    if(r <= val) return sum[k] - sum[p];
    int mid = l + r >> 1;
    int suml = sum[ls[k]] - sum[ls[p]];
    if(val > mid) return suml + query(rs[k], rs[p], mid + 1, r, val);
    else return query(ls[k], ls[p], l, mid, val);
}
int solve(int l, int r) {
    int nxt = 0;
    for(int i = 1; ; i = nxt + 1) {
        nxt = query(root[r], root[l - 1], 1, lim, i);//询问区间内<=i的数的和
        if(nxt < i) return i;
    }
}
int main() {
    n = read();
    for(int i = 1; i <= n; i++) a[i] = read(), lim = max(a[i], lim);
    for(int i = 1; i <= n; i++) insert(root[i], root[i - 1], 1, lim, a[i]);
    int q = read();
    while(q--) {
        int l = read(), r = read();
        printf("%d\n", solve(l, r));
    }
    return 0;
}