Dãy cấp số cộng
Xem dạng PDF
Gửi bài giải
Điểm:
1,33 (OI)
Giới hạn thời gian:
0.9s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Một dãy cấp số cộng là một dãy số mà 2 cặp phần tử liên tiếp bất kỳ có hiệu bằng nhau và khác 0. Trường hợp dãy số chỉ gồm 2 số khác nhau vẫn tính là một dãy cấp số cộng
Ví dụ:
- 2, 5 là dãy cấp số cộng.
- 8, 3 là dãy cấp số cộng.
- 1, 2, 3, 4, 5 là dãy cấp số cộng.
- 11, 8, 5, 2 là dãy cấp số cộng.
- 1, 2, 4, 5, 7 không phải là dãy cấp số cộng.
Cho một dãy số A gồm N số nguyên dương. Cho Q truy vấn dạng (x, y). Mỗi truy vấn yêu cầu kiểm tra xem đoạn từ x tới y có phải là hoán vị của một dãy cấp số cộng không.
Input
- Dòng đầu chứa 2 số nguyên ~N~, ~Q~.
- Số thứ ~i~ trong ~N~ số ở dòng thứ 2 là ~A_{i}~.
- Dòng thứ ~i~ trong ~Q~ dòng tiếp theo chứa 2 số nguyên ~x~, ~y~ mô tả truy vấn thứ ~i~.
Output
Gồm ~Q~ dòng.
- Dòng thứ ~i~ trong ~Q~ dòng sẽ trả lời cho truy vấn thứ ~i~.
- In ra YES nếu đoạn từ ~x~ tới ~y~ là hoán vị của một dãy cấp số cộng. Ngược lại thì ghi ra NO.
Giới hạn
11 test có ~N~, ~Q \le 1000~.
10 test có ~N \le 1000~, ~Q \le 10^{6}~.
10 test có ~N \le 10^{5}~, ~Q \le 10^{5}~.
~A_{i} \le 10^{9}~
Sample Input
5 2
1 3 2 5 4
1 5
2 4
Sample Output
YES
NO
Bình luận
segmentree co ban
Bài này làm được bằng segment tree không vậy mọi người :> Ý tưởng của mình là tìm giá trị lớn nhất và lớn nhất của đoạn cần truy vấn, sau đó tính tổng bằng công thức cấp số cộng và tổng của đoạn đó (mảng cộng dồn). Tất nhiên là mình vẫn chưa làm được :(
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
anh nguyen ton noi chi phai
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bài này làm như nào vậy bạn
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.