문제 링크
- http://icpc.me/5823
문제 출처
- 2011 IOI Day2 2번
사용 알고리즘
- Sqrt Decomposition
시간복잡도
- O(N sqrt N)
풀이
이동하는 것만 없다면 코끼리를 정렬해놓고 sqrt decomposition으로 하면 잘 될텐데, 이동하는 것이 거슬립니다.
sqrt decomposition은 O(N sqrt N)정도의 시간복잡도를 보장해줍니다. 코끼리가 이동을 하더라도 루트 시간이 보장되도록 하는 것은 간단한 아이디어를 추가해주면 됩니다.
sqrtN번의 업데이트마다 그룹을 O(N)시간에 다시 묶어준다면 O(N sqrt N) 시간이 보장됩니다. 각 버킷에는 최대 2sqrtN개의 코끼리가 존재할 수 있고, 다시 그룹을 묶어주는 것도 sqrtN번만 하기 때문에 루트 시간이 보장됩니다.