Editorial for Điểm chung
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1: Từ điều kiện "có điểm chung" của đề bài, ta chỉ cần quan tâm đến điểm trái dưới của các hình chữ nhật thuộc tập .
Điều kiện có điểm chung tương đương với điểm trái dưới nằm trong hình chữ nhật truy vấn (kể cả đường biên). Từ đó, ta chỉ cần kiểm tra và đếm số lượng điểm cho mỗi truy vấn.
Độ phức tạp:
Subtask 2: Ta có thể giải quyết bài toán bằng kỹ thuật Sweep Line kết hợp cấu trúc Segment Tree. Lưu ý rằng vì tọa độ có thể đạt nên ta cần lưu lại các giá trị quan trọng cần xét và sử dụng kỹ thuật Tìm kiếm nhị phân để giải quyết.
Độ phức tạp:
Comments