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

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\le l\le r<n$).

Ràng buộc

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

Ví dụ