Truy vấn Tòa nhà Có thể thấy

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $n$ tòa nhà xếp thành hàng. Một tòa nhà được gọi là có thể nhìn thấy (từ bên trái) nếu nó cao hơn tất cả các tòa nhà phía bên trái nó trong phạm vi xét. Xử lý $q$ truy vấn: mỗi truy vấn cho hai số $a, b$ — hỏi nếu chỉ có các tòa nhà từ $a$ đến $b$ , thì có bao nhiêu tòa nhà có thể nhìn thấy?

Dữ liệu vào

Dòng đầu: hai số nguyên $n$ và $q$ .
Dòng thứ hai: $n$ số nguyên $h_{1}, h_{2}, \dots, h_{n}$ là chiều cao các tòa nhà.
$q$ dòng tiếp theo: mỗi dòng chứa hai số $a$ và $b$ .

Dữ liệu ra

Với mỗi truy vấn, in ra số tòa nhà có thể nhìn thấy trong đoạn $[a, b]$ .

Ràng buộc

$1 \leq n \leq 10^{5}$
$1 \leq q \leq 2 \times 10^{5}$
$1 \leq h_{i} \leq 10^{9}$
$1 \leq a \leq b \leq n$

Ví dụ

Input	Output	Giải thích
5 3 4 1 2 2 3 1 5 2 5 3 4	1 3 1	Đoạn [1,5]: chỉ tòa 1 (cao nhất, không có gì bên trái). Đoạn [2,5] = [1,2,2,3]: tòa 2 (h=1 đầu tiên), tòa 3 (h=2 > 1), tòa 5 (h=3 > 2). Đoạn [3,4] = [2,2]: chỉ tòa 3 (h=2 đầu tiên).

Bình luận

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