Editorial for Lại là 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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Cách \(1\): Sắp xếp các khoảng, sử dụng statistic order tree.
ĐPT: \(O(nlogn)\)
Cách \(2\) (creator):
Coi mỗi khoảng là một điểm trong mặt phẳng hai chiều, cận dưới là hoành độ, cận trên là tung độ. Xây dựng cây phân đoạn hai chiều truy vấn số điểm trong một vùng chữ nhật.
Xét khoảng \(R\) tương ứng với điểm \(P\) . Các khoảng chứa \(R\) tương ứng với các điểm thuộc góc dưới bên phải điểm \(P\), các khoảng \(R\) chứa tương ứng với các điểm thuộc góc trên bên trái điểm \(P\).
ĐPT: \(O(n(logn)^2)\)
Comments