[질문] 이거 O(n^2)보다 빠른 방법 있음?

[익명(211.185)]

n개의 좌표가 (x, y)값이 주어질 때

각각의 점 (x_k, y_k)에 대해서 이 점보다 x와 y가 모두 작은 점이 있는지 확인하고 싶음

근데 x와 y에 대해 따로 정렬하고 찾으려고 하니까 1 + 2 + ... + n 해서 O(n^2) 걸리는거 같은데
더 빠른 방법 있나??

[익명(120.50)]

이분탐색

[p플랫(urd05)]

2d seg로 바로 풀리잖아~

[시아닌(kimjg1119)]

1d seg로도 되는데

[익명(121.188)]

ㅈㄴ 유명한 세그 문제. Nlogn으로 됨

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(211.185)]

좀만더...자세히 써주면 안될까 ㅠㅠ 세그같은거 안쓰고 싶은데 이분탐색은 암만생각해도 모르겠고

[익명(211.185)]

잉 지웠네..

[익명(119.70)]

정렬하고 이분탐색으로 x좌표 더 작은점 찾고 그 중에 y좌표 작은애들 찾으면 최대 (nlogn)아님?

[익명(211.185)]

음...........근데 x좌표가 더 작은점들의 집합에서 y좌표 이분탐색을 어떻게 하지...

[익명(112.185)]

오프라인 쿼리면 3차원도 가능합니다. 분할정복 솔루션이 있어요.

[익명(112.185)]

CDQ 알고리즘이요