AVLBIT - Dãy cấp số cộng

Giới hạn
  • Thời gian: 0.6s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua Codeforces (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên Codeforces. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên Codeforces

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.

Dữ liệu vào

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.

 

Dữ liệu ra

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.

Ràng buộc

11 test có N, Q <= 1000 .

10 test có N <= 1000, Q <= 10^6 .

10 test có N <= 10^5, Q <= 10^5.

A i <= 10^9

Ví dụ

Input
 5 2
 1 3 2 5 4
 1 5
 2 4

Output
 YES
 NO


 


  • Người up: cho_thanhan
  • Nguồn bài: Sưu tầm