테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== Milk Sum ======

===== 풀이 =====
  * 처음 주어진 상태에서 최대로 우유를 생산하는 방법은, 생산량이 많은 소를 가장 오랫동안 짜는 것이다. 소들을 정렬해놓고 앞에서부터 x1,x2,x3,... 을 해서 더한값이 총 생산량이 된다.
  * 값이 바뀌어도 이 원칙은 동일하다. 어떤 소의 생산량이 변경된다면 다시 정렬해서 똑같이 구하면 최대 생산량을 구할수 있다.
  * 하지만, 바뀐 원소가 하나라며 전체를 다시 정렬할 필요도 없다. 어떤 소의 생산량이 x에서 y로 변했다고 하자. 원래 x가 몇번째였는지, 그리고 y가 몇번째인지는 이분탐색으로 찾을수 있다. x는 i번째, y는 j번째라고 할때, 변경되는 값만 구해주면 된다. 우선 원래 생산량에서 x*i를 빼고, y*j를 더해줘야 한다. 그리고 j<i 라면, 원래 j번째부터 i-1번째까지 있던 소들의 순위는 1씩 늘어나게 된다. 이 말은, 이 소들이 1분씩 더 우유를 짜게 될 것이라는 뜻이니까, 총 생산량은 j부터 i-1번째까지를 더한만큼 늘려줘야 한다. 만약 i<j라면 반대로 i+1번째부터 j번째까지의 소들에 대해서 빼줘야 한다. 범위내에 소들의 생산량의 합은, 역시 누적합을 이용해서 O(1)에 처리 가능하다. 결국 쿼리당 시간 복잡도는 이분탐색에 걸리는 O(logn)이 된다.
  * 총 시간 복잡도는, 정렬하고 누적합을 구하는 전처리에 O(nlogn), q개의 쿼리를 처리하는데에 O(qlogn), 합쳐서 %%O((n+q)logn)%%이 된다
===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 28031. Milk Sum".

- Problem link: https://www.acmicpc.net/problem/28031
- Solution link: http://www.teferi.net/ps/problems/boj/28031

Tags: [prefix sum] [binary search]
"""

import bisect
import sys


def main():
    N = int(sys.stdin.readline())  # pylint: disable=unused-variable
    a = [int(x) for x in sys.stdin.readline().split()]

    sorted_cows = sorted(a)
    prefix_sum = [v := 0] + [v := v + x for x in sorted_cows]
    total_milk = sum(i * x for i, x in enumerate(sorted_cows, start=1))

    Q = int(sys.stdin.readline())
    for _ in range(Q):
        i, j = [int(x) for x in sys.stdin.readline().split()]
        cur_milk, next_milk = a[i - 1], j

        cur_pos = bisect.bisect_left(sorted_cows, cur_milk)
        next_pos = (
            bisect.bisect_left(sorted_cows, j)
            if next_milk <= cur_milk
            else bisect.bisect_right(sorted_cows, j) - 1
        )
        answer = (
            total_milk - cur_milk * (cur_pos + 1) + next_milk * (next_pos + 1)
        )
        if next_pos > cur_pos:
            answer -= prefix_sum[next_pos + 1] - prefix_sum[cur_pos + 1]
        else:
            answer += prefix_sum[cur_pos] - prefix_sum[next_pos]

        print(answer)


if __name__ == '__main__':
    main()

</dkpr>

{{tag>BOJ ps:problems:boj:골드_2}}