[BOJ] 백준 2820 자동차 공장

문제 링크

14268 내리갈굼 문제와 15782 Calculate! 2 문제와 같은 유형이다.

자세한 풀이는 링크를 들어가면 있다. 두개 다 보면 이해 간다.

세그먼트 트리를 이용하긴 하지만 쿼리는 구간이 아닌 한 정점에서만 물어보므로 lazy propagation을 단순히 O(lgN)의 시간복잡도로 해결하기 위해 사용한다.

따라서 세그먼트 트리에서 리프노드 이외의 노드의 값은 뭐가 들어있던 상관이 없기 때문에 코드의 29, 41번째 줄에서 v를 한 번만 더해줬다(리프노드에선 원래 한 번만 더해진다). 크게 상관있는 부분은 아니다.

정답 코드

질문 및 피드백 환영합니다.