문제 태그

• 세그먼트 트리
• lazy propagation
• 수식 정리
• 모듈러 연산

한국어 문제 해석

길이 N의 수열 A가 처음에 전부 0이다.

각 쿼리마다 어떤 구간에 값을 더한 뒤, 그 구간만 떼어 슬라임을 하나로 합칠 때의 최소 비용을 구한다.

슬라임 두 개의 무게가 x와 y이면 합칠 때 비용은 x 곱하기 y다. 매 쿼리마다 최소 총비용을 출력하면 된다.

문제 요약

• 구간 가산 업데이트가 누적된다.
• 매 쿼리마다 같은 구간의 최소 합치기 비용을 다시 계산해야 한다.
• 최소 비용은 구간합과 구간 제곱합만 알면 바로 구할 수 있다.

예시 워크스루

첫 번째 쿼리 뒤의 구간 값이 22, 22, 22라고 하자.

• 22와 22를 먼저 합치면 비용 484가 든다.
• 새 무게 44와 남은 22를 합치면 비용 968이 든다.
• 총비용은 1452다.

이 값을 다른 방식으로 보면, 서로 다른 두 슬라임을 한 번씩 짝지은 곱의 합과 같다.