원본 글 링크 : https://www.editorialhub.site/blog/2/post/116
EditorialHub
www.editorialhub.site
(에디토리얼 허브에도 같은 글을 작성했습니다)
주어진 수열에는 변화가 일어나지 않기 때문에 각 쿼리를 오프라인으로 처리한다고 생각할 수 있겠다. 쿼리들을 L의 오름차순으로 정렬을 시켜보자.
L을 1번 위치에 고정시켰을 때, 배열을 정렬시키기 위해 각 원소에 가해야 하는 연산의 양을 A[i]라고 한다면, O(N)의 시간 안에 해당 배열을 모두 채울 수 있을 것이다.
1번 위치에서 L을 한 칸 오른쪽으로 이동시켰을 때, A[i]에 나타나는 변화를 잘 관찰해보면, A[2]=0이 되고 오른쪽 원소들은 정확히 그만큼 2가 덜 곱해져도 되는 것이므로 A[2]만큼의 값이 계속 빠지다가, A[i]<A[2]가 되는 최초의 지점에서 멈춘다. 다시 A[i]만큼의 값이 A[j]<A[i](j>i)가 되는 최초의 지점까지 빠지고... 이것이 반복됨을 알 수 있다.
각각의 체인은 시작점~시작점보다 작은 값이 등장하는 최초의 위치 바로 이전까지 시작점에서의 값만큼을 빼줘야 하는 것이므로, 세그먼트 트리 위에서 걸어다니는 이분탐색을 활용하면 O(logN)안에 계산할 수 있다.
A[2]의 값은 최대 30이고, 다음 체인으로 넘어갈 때마다 시작점의 값이 1 이상씩 감소하므로 체인의 개수가 30개 이하임도 알 수 있다.
따라서 L을 한칸 오른쪽으로 이동했을 때 총 O(30logN)의 시간복잡도로 새로운 A를 계산할 수 있다. 같은 방법으로 L이 3으로 이동하는 경우, 4로 이동하는 경우...도 계산하면 된다.
이러한 방식으로 L을 한칸씩 오른쪽으로 옮기면서 정렬한 쿼리들을 순서대로 처리해나가면 문제를 풀 수 있다.
관찰이 재미있는 문제였다.
전체 시간복잡도(O(30∗NlogN))