Missing Coin Sum Queries

题目描述

你有 n 个面值为正整数的硬币。硬币编号为 1,2,\dots,n。 你的任务是处理 q 个查询，形式为：“如果你可以使用硬币 a \dots b，最小的无法凑出的和是多少？”

输入格式

第一行包含两个整数 n 和 q：硬币数量和查询数量。 第二行包含 n 个整数 x_1,x_2,\dots,x_n：每个硬币的面值。 接下来有 q 行描述查询。每行包含两个值 a 和 b：你可以使用硬币 a \dots b。

输出格式

对于每个查询输出答案。

5 3
2 9 1 2 7
2 4
4 4
1 5

4
1
6

提示

$1 \le n, q \le 2 \cdot 10^5$ $1 \le x_i \le 10^9$ $1 \le a \le b \le n$ 样例解释：第一次你可以使用硬币 [9,1,2]，然后是硬币 [2]，最后是硬币 [2,9,1,2,7]。

标签: CSES2184|区间查询

来源

CSES2184|区间查询