MathTrauma

문제 링크 : https://www.acmicpc.net/problem/22876 22876번: 츠바메가에시 "츠바메가에시"(つばめがえし)는 일본의 검사 "사사키 코지로"가 날아가는 제비를 베었다고 전해지는 검 초식의 이름이다. 기록상으로는 세 번 연속 칼질을 했다고 전해지나, 실제로 기술을 재 www.acmicpc.net 어릴 적 게임에서 보았던 이름을 보게 되어 반가운 마음으로 문제를 읽었는데... 후회했다. 매 번 세그먼트 트리를 설명할 수 없으니 세그먼트 트리에 대한 설명은 여기 를 참조하자. 일단 예외적인 경우부터, 행이나 열이 3 개 이하이면 모두 제거할 수 있으니 답은 전체 제비의 합이다. 위의 경우가 아니라면, 1 행을 제거하면 모든 열(수십만 개일 수 있는)에 합에 영향을 미치고(upda..

문제 링크 : https://www.acmicpc.net/problem/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net 보고 싶은 DVD 를 빼내서 가장 앞으로 가져다 놓는 작업을 한 번 하는 동안, 그 DVD 위에 있던 다른 것들은 자신 위에 쌓여 있던 개수가 모두 1 늘게 된다. 구간에 대해 update가 필요한 상황이니 세그먼트 트리나 펜윅 트리를 쓰고 싶은 생각이 들었다. 다만, 빼낸 DVD 를 옮겨 놓기 때문에 약간의 트릭이 필요했다. 쌓는다고 생각하지 말고 왼쪽부터 차례로 번호를 붙..

Range update 를 해야 하기 때문에 소위 Lazy Propagation 을 구현해야 하는데... 두 가지 다른 구현을 가지고 비교해 보기 위해 글을 쓴다. 두 구현의 우열을 논하는 것은 아니다. 이해하기 편한 쪽을 선택하면 되겠다. 구간 업데이트가 \( O(\log(n))\) 으로 동작하려면 어떻게 되어야 하는가? (1) node 의 관리 구간이 업데이트 구간에 포함되면 더 이상 하위 노드로 재귀 호출을 해서는 안된다. (2) 도달한 노드의 대표값은 업데이트 되어야만 한다.(그래야 상위 노드의 값도 제대로 된 값을 가지게 된다.) 위의 두 사항을 염두에 두고 있자. 1. 널리 쓰이는 구현 이제 흔히 보이는 lazy propagation 구현 코드부터 보자. 먼저 range update 를 수행하..