A6211. 「FJOI2016」神秘数
编程题
省选/NOI-
知识点
题目描述
一个可重复数字集合 $S$ 的神秘数定义为最小的不能被 $S$ 的子集的和表示的正整数。例如
```plain
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\cdots a_n$，$m$ 个询问，每次询问给定一个区间 $[l,r] \ (l\leq r)$，求由 $a_l,a_{l+1},\ldots,a_r$ 所构成的可重复数字集合的神秘数。
```plain
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\cdots a_n$，$m$ 个询问，每次询问给定一个区间 $[l,r] \ (l\leq r)$，求由 $a_l,a_{l+1},\ldots,a_r$ 所构成的可重复数字集合的神秘数。
输入格式
第一行一个整数 $n$，表示数字个数。
第二行 $n$ 个整数，从 $1$ 编号。
第三行一个整数 $m$，表示询问个数。
以下 $m$ 行，每行一对整数 $l,r$，表示一个询问。
第二行 $n$ 个整数，从 $1$ 编号。
第三行一个整数 $m$，表示询问个数。
以下 $m$ 行，每行一对整数 $l,r$，表示一个询问。
输出格式
对于每个询问，输出一行对应的答案。
输入输出样例
输入 #1
5 1 2 4 9 10 5 1 1 1 2 1 3 1 4 1 5
输出 #1
2 4 8 8 8
说明/提示
对于 $10 \%$ 的数据点，$n,m \leq 10$。
对于 $30 \%$ 的数据点，$n,m \leq 1000$。
对于 $60 \%$ 的数据点，$n,m \leq 50000$。
对于 $100 \%$ 的数据点，$n,m \leq 100000$，$\sum a_i \leq 10^9$。
对于 $30 \%$ 的数据点，$n,m \leq 1000$。
对于 $60 \%$ 的数据点，$n,m \leq 50000$。
对于 $100 \%$ 的数据点，$n,m \leq 100000$，$\sum a_i \leq 10^9$。