Chia dãy
Xem dạng PDF
Gửi bài giải
Điểm:
0,30 (OI)
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho dãy ~a_1, a_2, \dots, a_n~ gồm ~n~ số nguyên. Bạn cần trả lời ~q~ truy vấn, mỗi truy vấn gồm hai số nguyên ~l~, ~r~. Với mỗi truy vấn bạn cần đếm xem, có bao nhiêu cách chia dãy ~a_l, a_{l+1}, \dots, a_r~ thành hai phần khác rỗng sao cho mỗi phần gồm các phần tử đứng liên tiếp và đôi một phân biệt.
Input
Dòng đầu chứa hai số nguyên ~n~, ~q~ (~1 \le n, q \le 5 \times 10^5~).
Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9~).
~q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~l_i~, ~r_i~ (~1 \le l_i \le r_i \le n~) mô tả truy vấn thứ ~i~.
Output
In ra ~q~ dòng, dòng thứ ~i~ gồm một số nguyên là kết quả cho truy vấn thứ ~i~.
Sample Input 1
8 4
1 3 2 2 4 5 4 6
1 8
1 4
2 7
4 6
Sample Output 1
0
1
0
2
Bình luận
thuật đơn giản:https://ideone.com/5EPVWj