문제

• 
• 시간 제한: 1초
• 메모리 제한: 256MB

Problem Analysis

많은 부하를 빠르게 갱신해야 하는데, naive 하게 풀면 최대 O(N)이다. lazy propagation을 이용하면 O(logN)으로 줄일 수 있을 것이다. 그런데 문제는, 부하의 범위가 연속적이지 않을 수 있다는 점이다. 부하의 번호만 연속적으로 바꿀 수 있다면, lazy로 풀 수 있다.

Algorithm

1. Tree 형태로 입력을 받는다.
2. DFS를 통해서 번호를 재지정 하고, 각 직원의 부하 범위 또한 저장해준다.
3. 이대로는 깊이가 최대 N이 될 수 있으므로, 높이가 ceil(log2(N))인 segment Tree로 변경해준다.
4. 위의 정보를 가지고, Update시 Lazy Propagation을 사용한다.

Data Structure

• idxHash[]: original idx to new idx
• idxHash_reverse[]: new idx to original idx
• range_data: newIdx의 부하 범위를 저장
• ST[]: segment Tree
• lazy[]: lazy val 저장용

결과

Other