Editorial for Bedao Grand Contest 10 - PERFECT
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1+2
Có nhiều cách làm, một cách là: với mỗi truy vấn có thể dùng mảng đếm để đánh dấu những phần tử có trong đoạn, từ đó xét xem nó có phải là đoạn gồm các số liên tiếp hay không.
Một cách khác như sau:
Nhận xét: Một đoạn con là đoạn gồm những số liên tiếp khi và chỉ khi giá trị lớn nhất trừ giá trị nhỏ nhất bằng đúng độ dài của nó.
Vì vậy, có một cách trâu khác là tìm giá trị lớn nhất và giá trị nhỏ nhất trong đoạn rồi kiểm tra điều kiện giá trị lớn nhất trừ giá trị nhỏ nhất bằng đúng độ dài của nó có đúng hay không.
Subtask 3
Dựa vào cách thứ hai được nêu trong subtask trước, ta cần một thuật toán / cấu trúc dữ liệu để có thể tìm giá trị lớn nhất (nhỏ nhất) của 1 đoạn trong ~O(log~ ~n)~ hoặc ~O(1)~. Có nhiều cách để làm điều này, chẳng hạn như dùng Segment Tree, Binary Indexed Tree (BIT), hay Sparse Table.
Comments