문제 링크 14268 내리갈굼 문제와 15782 Calculate! 2 문제와 같은 유형이다.자세한 풀이는 링크를 들어가면 있다. 두개 다 보면 이해 간다. 세그먼트 트리를 이용하긴 하지만 쿼리는 구간이 아닌 한 정점에서만 물어보므로 lazy propagation을 단순히 O(lgN)의 시간복잡도로 해결하기 위해 사용한다.따라서 세그먼트 트리에서 리프노드 이외의 노드의 값은 뭐가 들어있던 상관이 없기 때문에 코드의 29, 41번째 줄에서 v를 한 번만 더해줬다(리프노드에선 원래 한 번만 더해진다). 크게 상관있는 부분은 아니다. 정답 코드 질문 및 피드백 환영합니다.
문제 링크 트리의 한 노드가 갈굼당하면 그 자식들이 모두 갈굼당해야한다. 구간이 보인다. 트리를 평평하게 펴서 세그먼트 트리로 만들고, lazy propagation을 적용하자.비슷한 문제로 15782 Calculate! 2 가 있다. 트리를 펴는 자세한 설명은 해당 링크를 보자. 위 링크와 차이점은 이번에는 pre-order로 순회했다는 것이다. 두 배열 $l$과 $r$, 주어진 트리의 어떤 정점 x에 대해 $l[x]$는 세그먼트 트리에서 x의 시작 구간이고 $r[x]$는 끝 구간이다. 이를 dfs로 쉽게 구할 수 있다.$l[x]$는 순회하는 순서로 값을 채워넣으면 된다.$r[x]$는 모든 자식들을 순회한 뒤 $l[x]$에서 자식 수만큼 증가시켜 넣어준다. (이는 세그먼트 트리에서 x의 마지막 자식의 ..
문제 링크 https://www.acmicpc.net/problem/15923 문제가 너무 쉬워서 설명할 게 없다. 방금 받은 좌표를 nx, ny라 하고 직전에 받은 좌표를 x, y라 하면 ans += abs(x+y-nx-ny) 이다. 내용이 너무 없으니 입출력 조건이라도 쓰자. 입력첫째 줄에 꼭지점의 개수 N이 주어진다. (4 ≤ N ≤ 20) 이후 둘째 줄 부터 N개의 줄에 걸쳐 꼭지점의 좌표 (x, y)가 주어진다. 좌표는 40 이하의 음이 아닌 정수이며, 중복되는 좌표는 주어지지 않는다.출력욱제가 설계한 건물의 둘레의 길이를 출력한다. 정답 코드