IOI 2011 Elephants

https://www.acmicpc.net/problem/5823

https://oj.uz/problem/view/IOI11_elephants

$O(N^{1.5})$ 풀이는 다른 블로그 등에서 찾아볼 수 있다.

$N$개의 점을 길이 $L$의 구간으로 덮을 때 최소 몇 개가 필요한지 묻는 문제이다. 이런 문제를 풀 때 먼저 할 수 있는 생각은 그래프 문제로 변환하는 것이다. 점이 $x$ 위치에 있다면, $x$에 검은 점을 두고 $x+L+1$에 흰 점을 두고 검은 점에서 흰 점으로 길이 1의 간선을 잇자. 그리고 모든 흰 점에서 자신의 직후에 있는 점으로 향하는 길이 0의 간선을 잇자. 이제 구하는 답은 가장 왼쪽의 점에서 가장 오른쪽 점까지 가는 최단거리가 된다. 모든 점에서 나오는 간선이 한 개 이하이며, 오른쪽을 향하기 때문에 이 그래프는 트리가 된다. 이 트리에서 루트와 가장 왼쪽 점의 최단거리를 구하는 것은 link/cut tree로 해결할 수 있다. 코끼리의 위치 변경 쿼리가 들어왔을 때는 검은 점 하나와 흰 점 하나의 위치가 바뀌는데, 두 점의 차수는 합쳐서 최대 5로, 상수이다. 쿼리가 들어올 때마다 상수 개의 간선을 바꾸어 처리할 수 있으므로, 시간복잡도는 $O((N+Q)\log N)$이 된다.