Editorial for Bedao Grand Contest 10 - PERFECT


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

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

Please read the guidelines before commenting.


There are no comments at the moment.