CSES2184 缺失硬币总和查询
#CS2184. 缺失硬币总和查询
缺失硬币总和查询
题目背景
翻译自 CSES-2184 题。
题目描述
你有 n 个硬币，每个硬币有一个正整数的面值。硬币的编号为 1,2,…,n1, 2, \dots, n1,2,…,n。
你的任务是处理 q 个查询，每个查询的形式是：“如果你可以使用硬币 a 到 b，那么无法构成的最小总和是多少？”
输入格式
第一行包含两个整数 n 和 q：分别表示硬币的数量和查询的数量。
第二行包含 n 个整数 x1,x2,…,xnx_1, x_2, \dots, x_nx1,x2,…,xn，表示每个硬币的面值。
接下来有 q 行，每行包含两个整数 a 和 b，表示你可以使用从硬币 a 到硬币 b（包含这两个硬币）的所有硬币。
输出格式
对于每个查询，输出你无法用所选硬币构成的最小总和。
样例
5 3
2 9 1 2 7
2 4
4 4
1 5
4
1
6
样例1解释
-
第一个查询，你可以使用硬币 [9,1,2][9, 1, 2][9,1,2]，最小无法构成的总和是 4。
-
第二个查询，你可以使用硬币 [2][2][2]，最小无法构成的总和是 1。
-
第三个查询，你可以使用硬币 [2,9,1,2,7][2, 9, 1, 2, 7][2,9,1,2,7]，最小无法构成的总和是 6。
说明/提示
1≤xi≤1091 \leq x_i \leq 10^91≤xi≤109；