티스토리 뷰

IOI/IOI2014

[IOI2014 Day1] Wall 해법

전명우 2014.07.17 01:20

Segment Tree를 이용하여 해결하는 문제다.


Segment Tree의 각 노드별로 구간 내에서 최소값과 최대값을 가지고 있는다. add 연산은 lower boundary(최소값)을 변화시키고, remove 연산은 upper boundary(최대값)을 변화시킨다. Segment Tree를 순회할 때 자신(현재 탐색 중인 노드)의 조상에 대한 값을 자신한테 반영할 수 있도록 신경쓴다.


각 노드의 값 갱신에 대해 자세한 설명은 생략한다. 첨부된 소스를 참고하길 바란다.


$K$개의 쿼리마다 계산하는 시간복잡도는 $O(lg N)$이며, 최종적으로 각 위치에 대한 높이를 계산하는 시간복잡도는 $O(N)$이다. 그러므로 총 문제를 해결하는 시간복잡도는 $O(K lg N + N)$이다.


코드 보기

저작자 표시
신고

'IOI > IOI2014' 카테고리의 다른 글

[IOI2014 Day2] Gondola 해법  (0) 2014.07.17
IOI2014 Day 2 종료  (0) 2014.07.17
[IOI2014 Day1] Rail 해법  (0) 2014.07.17
[IOI2014 Day1] Game 해법  (1) 2014.07.17
[IOI2014 Day1] Wall 해법  (0) 2014.07.17
IOI2014  (0) 2014.07.17
댓글
댓글쓰기 폼