Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom10月前

09/11
13:05
主席树

[bzoj 4408] [Fjoi 2016]神秘数

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13},
1 = 1
2 = 1+1
3 = 1+1+1
4 = 4
5 = 4+1
6 = 4+1+1
7 = 4+1+1+1
8无法表示为集合S的子集的和,故集合S的神秘数为8。
现给定n个正整数a[1]..a[n],m个询问,每次询问给定一个区间[l,r](l<=r),求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行一个整数n,表示数字个数。
第二行n个整数,从1编号。
第三行一个整数m,表示询问个数。
以下m行,每行一对整数l,r,表示一个询问。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

对于每个询问,输出一行对应的答案。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

5
1 2 4 9 10
5
1 1
1 2
1 3
1 4
1 5

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

2
4
8
8
8

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

对于100%的数据点,n,m <= 100000,∑a[i] <= 10^9

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

假设当前的神秘数是ans,加进来一个a,如果a<=ans,则ans变成ans+a,否则ans不变

所以ans从1开始,每次统计小于等于ans的数的和sum,并把ans变成sum+1,求和可以用可持久化线段树维护

c++:

pascal:

 

[bzoj 4408] [Fjoi 2016]神秘数