Editorial for Kiểm tra phạm vi


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: old_creator

Ý tưởng: sắp xếp dãy ngoặc theo cận dưới.

Ta tạo cấu trúc dữ liệu để diễn đạt một khoảng: left, right, idx lần lượt là cận dưới, cận trên, chỉ số (vị trí) của khoảng trong dãy.

Sắp xếp dãy ngoặc theo chiều tăng dần của left, nếu hai khoảng có left bằng nhau khoảng có right lớn hơn được ưu tiên xếp trước.

Tạo mảng \(contained[]\) có ý nghĩa khoảng chỉ số \(i\) trong mảng ban đầu bị chứa. Khởi tạo biến lưu max cận trên (âm vô cùng) rồi duyệt qua từng khoảng (đã được sắp xếp): Nếu cận trên khoảng đang xét không lớn hơn max cận trên thì khoảng bị chứa, sử dụng thuộc tính idx đánh dấu khoảng đang xét trong mảng contained rồi cập nhật max cận trên.

Tạo mảng \(contain[]\) có ý nghĩa khoảng chỉ số \(i\) trong mảng ban đầu chứa một khoảng nào đó. Khởi tạo biến lưu min cận trên (dương vô cùng) rồi duyệt qua từng khoảng (đã được sắp xếp) theo chiều ngược: Nếu cận trên khoảng đang xét không nhỏ hơn min cận dưới thì khoảng có chứa, sử dụng thuộc tính idx đánh dấu khoảng đang xét trong mảng contain rồi cập nhật min cận trên.

Kết quả cuối cùng là các giá trị trong mảng \(contain[]\) và \(contained[]\).

Ghi chú: Bài toán có thể giải theo bất kì chiều sắp xếp nào.

ĐPT: \(O(n)\).


Comments

There are no comments at the moment.