PS 이야기

우선, 이 문제에 대해 본격적으로 설명하기에 앞서 이 문제에서 특성을 몇 가지 설명하겠다. $d(i,j)$를 정류장 $i$와 정류장 $j$ 사이의 거리라고 할 때, $d(i,j) = d(j,i)$ 이다.맨 왼쪽 정류장은 C type 이다.맨 오른쪽 정류장은 D type 이다. $i > 0$인 $i$에 대하여 $d(0,i)$ 를 모두 구한다. 이 때 $d(0,i)$가 최소가 되는 $i$를 $x$라 하자. 이 때 정류장 $x$는 정류장 $0$ 보다 오른쪽에 있으면서 가장 가까운 D type 정류장이다. 만약 $d(0,i) = d(0,x)+d(x,i)$ 라면 정류장 $i$는 정류장 $x$ 보다 왼쪽에 있다. 이 문제를 해결하기 위해, 정류장 $x$를 기준으로 왼쪽에 있는 것과 오른쪽에 있는 것들을 나눠 따로 ..

여러 가지 다양한 해법이 있다고 생각한다. $0$번 도시 부터 $N-1$번 도시까지 총 $N$개의 도시가 있다. 이 $N$개의 도시들을 단말 노드로 갖는 이진 트리를 만든다. 이 이진트리의 단말 노드의 개수는 정확히 $N$개이다. 이제 모든 $(i,j)$ 쌍 ($0 \leq i < j \leq N-1$)에 대하여 단말 노드 $i$와 단말 노드 $j$의 LCA(Lowest Common Ancestor, 최저 공통 조상)를 $k$라 했을 때, left[k]에 1을 더한다. 쿼리(질문)가 $(u,v)$으로 주어졌을 때, 단말 노드 $u$와 단말 노드 $v$의 LCA를 $w$라 했을 때, left[w] 값을 1 감소 시키고, 그 값이 0 이면, 값을 1 반환하고 감소한 뒤 그 값이 여전히 0 보다 크다면 0을 ..

Segment Tree를 이용하여 해결하는 문제다. Segment Tree의 각 노드별로 구간 내에서 최소값과 최대값을 가지고 있는다. add 연산은 lower boundary(최소값)을 변화시키고, remove 연산은 upper boundary(최대값)을 변화시킨다. Segment Tree를 순회할 때 자신(현재 탐색 중인 노드)의 조상에 대한 값을 자신한테 반영할 수 있도록 신경쓴다. 각 노드의 값 갱신에 대해 자세한 설명은 생략한다. 첨부된 소스를 참고하길 바란다. $K$개의 쿼리마다 계산하는 시간복잡도는 $O(lg N)$이며, 최종적으로 각 위치에 대한 높이를 계산하는 시간복잡도는 $O(N)$이다. 그러므로 총 문제를 해결하는 시간복잡도는 $O(K lg N + N)$이다. #include #inc..