Truy Vấn Giá Trị Nhỏ Nhất

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Java, Python

Cho mảng $a$ gồm $n$ số nguyên (đánh số từ $0$ ). Trả lời $q$ truy vấn, mỗi truy vấn cho hai số $l, r$ và yêu cầu tìm giá trị nhỏ nhất trong đoạn $a [l], a [l + 1], \dots, a [r]$ .

Hàm cần cài đặt

Đây là bài toán signature grader. Bạn chỉ cần cài đặt hai hàm sau, không cần viết main() hay đọc/ghi dữ liệu.

Ngôn ngữ hỗ trợ: C/C++, Python, và Java.

C++

void init(int n, int arr[]);
int query(int l, int r);

Python

def init(n: int, arr: list[int]) -> None: ...
def query(l: int, r: int) -> int: ...

Java

public class Solution {
    public void init(int n, int[] arr) { ... }
    public int query(int l, int r) { ... }
}

Mô tả

init(n, arr): Được gọi một lần trước tất cả các truy vấn. n là số phần tử, arr là mảng gồm $n$ số nguyên đánh số từ $0$ đến $n - 1$ .
query(l, r): Được gọi $q$ lần. Trả về giá trị nhỏ nhất trong $a [l], a [l + 1], \dots, a [r]$ ( $0 \leq l \leq r < n$ ).

Ràng buộc

$1 \leq n, q \leq 2 \cdot 10^{5}$
$1 \leq a [i] \leq 10^{9}$
$0 \leq l \leq r < n$

Ví dụ

Input	Output	Giải thích
5 3 3 1 4 1 5 0 4 1 3 2 2	1 1 4	min(3,1,4,1,5)=1, min(1,4,1)=1, min(4)=4

Bình luận

Không có bình luận tại thời điểm này.