#508. ITRMQSEQ – Truy vấn Minimum trên dãy số

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Cho dãy số nguyên gồm n phần tử a_1, a_2, …, a_n Q truy vấn. Mỗi truy vấn có dạng một cặp số nguyên u, v . Với mỗi truy vấn u, v , bạn cần trả lời câu hỏi số nhỏ nhất trong các số từ số thứ u tới số thứ v là bao nhiêu?

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên dương n Q ;
  • Dòng thứ hai chứa n số nguyên a_1, a_2, …, a_n ;
  • Q dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v .

Hai số liên tiếp trên một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra:

  • Ghi trên một dòng Q số nguyên, mỗi số là câu trả lời cho một truy vấn (theo đúng thứ tự), hai số liên tiếp cách nhau một dấu cách.

Ví dụ:

Dữ liệu vào:
5 3
2 -1 5 3 -3
1 3
3 4
1 5
Dữ liệu ra:
-1 3 -3

Giới hạn:

  • 1 ≤ n ≤ 10^6; 1 ≤ u ≤ v ≤ n; 1 ≤ Q ≤ 10^5; |a_i| ≤ 10^9 .