CSES - Missing Coin Sum Queries | Truy vấn tổng đồng xu bị thiếu

Xem PDF
Tác giả:
ngpin_04
Dạng bài
Điểm: 2000 (p) Thời gian: 2.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn có \(n\) đồng xu với các giá trị số nguyên dương. Các đồng xu được đánh số \(1,2,\ldots,n\).

Nhiệm vụ của bạn là xử lý \(q\) truy vấn có dạng: "nếu bạn có thể sử dụng các đồng xu \(a\ldots b\), số tiền nhỏ nhất mà bạn không thể tạo ra là gì?"

Input

  • Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(q\): số lượng đông xu và truy vấn.
  • Dòng thứ hai có n số nguyên \(x_1,x_2,\ldots,x_n\): giá trị của mỗi đồng xu.
  • Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng có hai giá trị \(a\) và \(b\): bạn có thể sử dụng các đồng xu \(a\ldots b\).

Output

  • In câu trả lời cho từng truy vấn.

Constraints

  • \(1 \leq n,q \leq 2 \cdot 10^5\)
  • \(1 \leq x_i \leq 10^9\)
  • \(1 \leq a \leq b \leq n\)

Example

Sample input

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

Sample output

4
1
6

Note

Đầu tiên bạn có thể sử dụng các đồng xu \([9,1,2]\), sau đó là các đồng xu \([2]\) và cuối cùng là các đồng xu \([2,9,1,2,7]\).

Bình luận


  • 1
    vanphukhang_0604    11:55 a.m. 16 Tháng 8, 2023 ← chỉnh sửa 4

    CSES - Missing Coin Sum Queries | Truy vấn tổng đồng xu bị thiếu

    Bạn có \(n\) đồng xu có giá trị nguyên dương. Các đồng xu được đánh số \(1, 2, \ldots, n\).

    Nhiệm vụ của bạn là xử lý \(q\) truy vấn có dạng: "nếu bạn có thể sử dụng các đồng xu \(a\ldots b\), số tiền nhỏ nhất mà bạn không thể lấy được là bao nhiêu?"

    Input

    • Dòng đầu tiên chứa hai số nguyên \(n\) và \(q \ (1 \leq n, q \leq 2 \cdot 10^5)\): số lượng đồng xu và truy vấn.
    • Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2, \ldots, x_n \ (1 \leq x_i \leq 10^9)\): giá trị của mỗi đồng xu.
    • \(q\) dòng cuối mô tả các truy vấn. Mỗi dòng có hai giá trị \(a\) và \(b \ (1 \leq a \leq b \leq n)\): bạn có thể sử dụng các đồng xu \(a\ldots b\).

    Output

    • In ra \(q\) dòng trả lời cho \(q\) truy vấn.

    Example

    Test 1

    Input 
    5 3
2 9 1 2 7
2 4
4 4
1 5
    Output 
    4
1
6
    Note

    Giải thích: Ở truy vấn đầu tiên bạn có thể sử dụng các đồng xu \([9, 1, 2]\), ở truy vấn thứ hai là đồng xu \([2]\) và ở truy vấn cuối cùng là các đồng xu \([2, 9, 1, 2, 7]\).