首页 > 代码库 > [CC FBR] Forbidden Sum

[CC FBR] Forbidden Sum

2024-11-23 02:40:01   202人阅读

题意

　　对多重数集 S 定义 Forbidden Sum F(S): 最小的无法凑出的自然数.

　　即 $F(S) = \min_x [\not \exists T \subset S, ~s.t.~ \sum_{i \in T} i = x]$ .

　　

　　给定长度为 n 的数列 A .

　　m 组询问 [l, r] , 求 F(A[l : r]) .

 

　　n, m <= 100000 .

　　1 <= a[i] <= 10 ^ 9 .

　　1 <= a[1] + a[2] + ... + a[n] <= 10 ^ 9 .

 

分析

　　我们先考虑如何求一个集合 S 的 F 值.

 

　　探究 Forbidden Sum 的性质, 以更好的解决问题.

　　对于一个数集 S ,  F(S) = x , 考虑 F( S + {w} ) 怎么求.

　　我们可以多凑出 w, w+1, w+2, ..., w+x .

　　若 w <= x+1 , 那么 F( S + {w} ) = F(S) + w , 反之不变.

 

　　那么, 我们可以将 S 中的值 b[1], b[2], ..., b[m] 从小到大进行排序.

　　从小到大逐个尝试添加, 直到添加失败.

　　b[1] <= sum[0] + 1

　　b[2] <= sum[1] + 1

　　b[3] <= sum[2] + 1

　　...

　　b[x] <= sum[x-1] + 1

　　b[x+1] > sum[x] + 1

　　那么 F(S) = sum[x] + 1 .

 

　　修改一下这个算法.

　　对于 sum[x] + 1 , 我们每次找到最大的 i , x < i <= n, 使得 b[i] <= sum[x] + 1 , 然后令 x = i 进行迭代.

　　发现这样我们就可以二分查找最大的 i , 同时查找的次数是 log W .

 

　　考虑在序列 A 中进行询问.

　　我们只需要用 可持久化线段树 执行上述算法即可.

　　时间复杂度为 O(n log n log W) .

 

　　实现的时候只用查询值在 [lastsum + 1, sum] 中的和, 如果和为 0 , 那么就找不到, 否则令 lastsum = sum, sum += D .

　　初始 lastsum = 0, sum = 1 .

 

实现

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cctype>
 5 #define F(i, a, b) for (register int i = (a); i <= (b); i++)
 6 
 7 namespace Input {
 8     const int S = 2000000;
 9     char s[S], *h = s+S, *t = h;
10     inline char getchr(void) { if (h == t) fread(s, 1, S, stdin), h = s; return *h++; }
11     inline int rd(void) {
12         int f = 1; char c = getchr(); for (; !isdigit(c); c = getchr()) if (c == ‘-‘) f = -1;
13         int x = 0; for (; isdigit(c); c = getchr()) x = x*10+c-‘0‘; return x*f;
14     }
15 }
16 using Input::rd;
17 
18 const int N = 100005;
19 const int R = (int)1e9;
20 const int S = 5000000;        // n * log(1e9)
21 
22 #define LC (c[x][0])
23 #define RC (c[x][1])
24 #define M ((L + R) >> 1)
25 
26 int n, tot, rt[N];
27 int c[S][2], sum[S];
28 
29 inline int Insert(int f, int L, int R, int w) {
30     int x = ++tot; LC = c[f][0], RC = c[f][1], sum[x] = sum[f];
31     if (L == R) return sum[x] += w, x;
32     w <= M ? LC = Insert(c[f][0], L, M, w) : RC = Insert(c[f][1], M+1, R, w);
33     sum[x] = sum[LC] + sum[RC];
34     return x;
35 }
36 
37 inline int Sum(int rootL, int rootR, int L, int R, int l, int r) {
38     if (l <= L && R <= r) return sum[rootR] - sum[rootL];
39     int res = 0;
40     if (l <= M) res += Sum(c[rootL][0], c[rootR][0], L, M, l, r);
41     if (M < r) res += Sum(c[rootL][1], c[rootR][1], M+1, R, l, r);
42     return res;
43 }
44 
45 int Calc(int l, int r) {
46     int sum = 1, last = 0;
47     while (true) {
48         int D = Sum(rt[l-1], rt[r], 1, R, last + 1, sum);
49         if (!D) break;
50         last = sum, sum += D;
51     }
52     return sum;
53 }
54 
55 int main(void) {
56     #ifndef ONLINE_JUDGE
57         freopen("xsy1175.in", "r", stdin);
58     #endif
59     
60     n = rd();
61     F(i, 1, n) {
62         int x = rd();
63         rt[i] = Insert(rt[i-1], 1, R, x);
64     }
65     
66     int m = rd();
67     F(i, 1, m) {
68         int l = rd(), r = rd();
69         printf("%d\n", Calc(l, r));
70     }
71     
72     return 0;
73 }

 

[CC FBR] Forbidden Sum


联系
我们