티스토리 뷰
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
링크
TAG
- BOI 2001
- idea
- Splay Tree
- USACO
- z-trening
- Divide & Conquer
- majority
- dynamic programming
- IOI2012
- BOI 2009
- Greedy Method
- Tree
- TRIE
- Dijkstra
- Parametric Search
- Boyer-Moore Majority Vote Algorithm
- moore
- BOI
- HackerRank
- ioi
- IOI2011
- Algorithm
- Dynamic Pramming
- IOI2013
- Segment tree
- IOI2014
- vote
- optimization
- Knuth Optimization
- Boyer
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함