#T2143. 缺失硬币和查询(Missing Coin Sum Queries)

缺失硬币和查询(Missing Coin Sum Queries)

链接: https://cses.fi/problemset/task/2184

板块: Range Queries

时限: 1.00 s | 内存: 512 MB

题目描述

你有 nn 枚面值均为正整数的硬币。硬币编号为 1,2,…,n1,2,\dots,n。

你的任务是处理 qq 个如下形式的查询:"如果你可以使用硬币 a…ba \dots b,你无法凑出的最小和是多少?"

输入

第一行输入包含两个整数 nn 和 qq:分别表示硬币数量和查询数量。

第二行包含 nn 个整数 x1,x2,…,xnx_1,x_2,\dots,x_n:每枚硬币的面值。

最后有 qq 行描述查询。每行包含两个值 aa 和 bb:你可以使用硬币 a…ba \dots b。

输出

对每个查询输出其答案。

数据范围

1≤n,q≤2⋅1051 \le n, q \le 2 \cdot 10^5 1≤xi≤1091 \le x_i \le 10^9 1≤a≤b≤n1 \le a \le b \le n

样例输入

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

样例输出

4
1
6