pjh1016   2년 전

주어지는 직사각형들의 왼쪽 변과 오른쪽 변에 대해 스위핑해가며 개수를 구했습니다.

세그먼트 트리의 노드에는 y좌표 구간에 방문하는 횟수를 저장하고, 왼쪽 변이면 해당 구간에 +1, 오른쪽 변이면 -1을 더해주었습니다.

구간 업데이트를 해야해서 lazy propagation을 이용하였습니다.

---

구현하면서 다음 상황들을 고려하였습니다.

1. 퍼레이드 영역으로 수직한 선분이 주어지는 경우 (x x y1 y2)

만약 왼쪽 변만 있으면 세그먼트 트리를 먼저 업데이트한 뒤, 개수를 구하고

오른쪽 변만 있으면 개수를 구한 다음에 세그먼트 트리를 업데이트하였습니다.

첫 번째 경우를 처리해주기 위해 어떤 x좌표에 왼쪽 변과 오른쪽 변이 둘 다 있는 경우를 따로 처리하였습니다.

이 경우에는 왼쪽 변을 트리에 업데이트, 개수 구하기, 오른쪽 변을 트리에 업데이트 순으로 처리하였습니다.

2. 동일한 x좌표값을 갖는 변이 여러 개인 경우

동일한 좌표에 변이 여러 개 있으면 한 번에 처리해주었습니다.

---

생각해볼 수 있는 예시들을 정말 다 해본 것 같은데 반례를 찾지 못해겠어서 처음으로 질문글 올립니다 ㅜㅜ

아니면 풀이의 로직 자체에서 허점이 있다면 알려주세요..

이틀째 이 문제에서 벗어나지 못하고 있습니다.

rkaxhdals   2년 전

우선 83, 93, 102번 라인의 M을 C로 바꾸셔야 할 듯 하구요..

1
1 2
2 3
1 4 1 5
3 5 2 4

위와 같은 반례를 한번 생각해보시길 바랍니다.

pjh1016   2년 전

반례 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.