IOI18 meetings

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

길이 의 수열 가 있을 때, ~에서의 ‘모임 비용’의 최솟값을 구해야 한다.

이때 모임 비용 는 다음과 같이 정의된다.

여기에서 를 모임 장소라고 한다.

수열의 길이 과 쿼리의 개수 는 이하, 시간 제한은 4.5s이다.풀이

 일단 모든 수들에 서로 다른 작은 수를 더하면 되므로 모든 수들이 다르다고 가정해도 된다.

쿼리 에 대해서 로 정의하면, 답은 이 된다.

 가 보다 작을 때와 클 때를 나눈 것이다.

이 사실을 통해 쿼리 을 쿼리 과 으로 나눌 수 있다.

이 쿼리 중 들을 모두 구할 수 있다면 은 수열을 뒤집어서 똑같이 구할 수 있다.

이제 쿼리 만 모아서 다시 으로 쓰자.

이 들이 가지는 중요한 특징은 모든 에 대해서 을 만족한다는 것이다.

다음과 같은 함수를 정의하자.

= 인 모든 쿼리를 처리하고, 를 반환하는 함수 (단, 모든 에 대해 을 만족해야 한다.)

라고 했을 때, process(M + 1, E)의 반환값 를 안다면, 인 쿼리들의 값을 모두 알 수 있다. 따라서 에서 과 를 호출하면 인 모든 쿼리를 처리하는 것이 가능하다.

문제는 를 구해야 한다는 것이다. segment tree의 각 노드에 CHT를 사용하여 에 처리하거나, Li Chao Segment Tree를 사용하여 에 처리할 수 있지만, 100점을 받기는 쉽지 않다. (Li-Chao tree를 사용한 방법이 oj.uz에서 4.7s가 나온다) 를 에 처리하기 위해 증명할 다음과 같은 중요한 성질이 있다.

 를 쿼리 에서의 최적 모임 장소들 중 가장 왼쪽에 있는 모임 장소라고 할 때, 는 단조 증가한다.

쿼리 의 모임 비용은 쿼리 에서의 비용과 번 사람이 모임 장소까지 가는 비용의 합이 된다.

쿼리 에서의 비용은 모임 장소가 최적해에서 왼쪽으로 가면 증가한다. 또한 번 사람이 모임 장소까지 가는 비용도 왼쪽으로 갈수록 단조 증가한다. 따라서 그 합도 왼쪽으로 가면 증가할 것이고, 는 감소할 수 없다.

에서의 를 , 에서의 를 라고 하자.

의 값은 일 때는 의 값과 같으므로 따로 구해줄 필요가 없다. 은 이다. 문제는 일 때이다.

위에서 증명한 성질에 의해, 어떤 가 존재하여 인 에서는 모임 장소가 에 있고, 인 에서는 모임 장소가 에 있을 것이다. 모임 장소가 에 있다면 최소 비용은 으로 계산된다. 이것은 하나의 직선으로 표현될 수 있다. 모임 장소가 에 있다면 최소 비용은 로 계산된다. 이것은 에 상수를 더한 값이다.

를 직선의 deque과 더해진 상수 로 관리하면 모든 연산을 총 에 할 수 있다.

해야 하는 연산은 다음과 같다.

1. 의 front에 직선을 추가 : front의 직선부터 보면서 추가된 직선과 비교한다. 추가된 직선이 더 비용이 낮다면 원래 직선을 빼고 반복하며, 원래 있던 직선의 비용이 낮다면 그 앞에 추가된 직선을 넣어줄 수 있다. 위의 증명에 의해 deque의 앞에 있는 직선들만 봐도 충분하다. 한 번의 연산에 최소 한 개의 직선이 없어지므로 amortized 이 된다.

2. 에 상수를 더함 : 에 더해주면 된다. 내부의 값이 필요할 때 직선에 를 더해서 사용하고, 내부에 직선을 넣을 때는 를 뺀 후 넣어주면 된다. 에 처리할 수 있다.

3. 두 개의 를 합침 : 작은 deque에서 하나씩 빼서 큰 deque에 넣어주는 방식으로 합칠 수 있다. 잘 알려진 방법으로 시간복잡도는 amortized 이 된다.

4. 의 값을 구함 : 이분 탐색을 통해 에서 값을 담당하는 직선을 에 찾을 수 있다. 쿼리마다 한 번 구하므로 이다. 

따라서 시간복잡도 , 공간복잡도 에 문제를 해결할 수 있다.