티스토리 뷰

IOI/IOI2014

[IOI2014 Day1] Wall 해법

전명우 2014. 7. 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 해법  (3) 2014.07.17
IOI2014  (0) 2014.07.17
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함