BOJ '바리스타와 함께하는 대회 테스트' 풀이
Main Page / Scoreboard A. 농부 후안은 바리스타입니다 2차원 fenwick tree를 이용하여 O(Q log N log M)에 해결할 수 있다. [x1, y1]×[x2, y2] 영역에 +d하는 연산을, (x1, y1)와 (x2+1, y2+1)에 +d하고 (x1, y2+1)와 (x2+1, y1)에는 -d하는 연산으로 치환한다. 이렇게 치환한 상황에서 (x, y)에 위치한 씨앗의 개수는 [1, x]×[1, y]에 있는 씨앗의 개수를 계산하는 연산으로 치환된다. 아래의 코드를 참고하자. B. 로스팅하는 엠마도 바리스타입니다 어떤 정점 X를 루트로 하는 트리를 가정하자. 이 때 다른 정점들에서 X로 이르는 최단거리의 합 S(X)에 대해 관찰하자. 트리에서 임의의 두 정점 사이를 잇는 경로는 ..
2018. 4. 9.
