Không Có Thời Gian Chờ Khô

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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$ đoạn hàng rào liên tiếp, mỗi đoạn cần được sơn một màu nhất định. Màu được đánh số từ $1$ đến $N$ theo thứ tự độ đậm tăng dần (màu $1$ nhạt nhất, màu $N$ đậm nhất). Ban đầu tất cả các đoạn chưa được sơn màu nào.

Một nét sơn có thể sơn một đoạn liên tiếp bất kỳ với một màu duy nhất, với điều kiện không được sơn màu nhạt hơn lên vùng đã có màu đậm hơn (chỉ được sơn màu đậm hơn lên màu nhạt hơn, không được ngược lại).

Có $Q$ truy vấn độc lập với nhau. Mỗi truy vấn cho một đoạn $[a, b]$ : hỏi cần ít nhất bao nhiêu nét sơn để hoàn thành màu cho tất cả các đoạn trong $[a, b]$ đúng như yêu cầu, trong khi không sơn vào bất kỳ đoạn nào ngoài $[a, b]$ ?

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $Q$ .

Dòng thứ hai chứa $N$ số nguyên $c_{1}, c_{2}, \dots, c_{N}$ — màu mong muốn của từng đoạn hàng rào.

$Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ mô tả một truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in ra một số nguyên duy nhất trên một dòng.

Ràng buộc

$1 \leq N, Q \leq 2 \times 10^{5}$
$1 \leq c_{i} \leq N$
$1 \leq a \leq b \leq N$

Ví dụ

Input	Output	Giải thích
8 4 1 2 2 1 1 2 3 2 4 6 3 6 1 6 5 8	2 3 3 3	Truy vấn $[4, 6]$ tương ứng với dãy $1 1 2$ : cần 2 nét. Truy vấn $[3, 6]$ tương ứng $2 1 1 2$ : cần 3 nét. Truy vấn $[1, 6]$ tương ứng $1 2 2 1 1 2$ : cần 3 nét. Truy vấn $[5, 8]$ tương ứng $1 2 3 2$ : cần 3 nét.

Ghi chú

Mỗi truy vấn được xử lý độc lập — kết quả của truy vấn này không ảnh hưởng đến truy vấn khác.

Bình luận

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