BOJ 16909: 카드 구매하기 3

Link

• https://www.acmicpc.net/problem/16909

Tag

• 스택

Time Complexity

• $O(N)$

수열 $A$가 주어지고, $A$의 모든 구간 $[s,e]$의 최댓값-최솟값의 총 합을 구하는 문제다.

최댓값의 총 합과 최솟값의 총 합을 각각 구하자.

각각의 $A_i$에 대해 $A_i$보다 왼쪽에 있으면서 $A_i$보다 큰 수 중 가장 오른쪽에 있는 수의 인덱스를 $s_i$, $A_i$보다 오른쪽에 있으면서 $A_i$보다 큰 수 중 가장 왼쪽에 있는 수의 인덱스를 $e_i$이라 하자. 그러면 구간 $[a,b]$ $(s_i \le a \le i \le b \le e_i)$ 의 최댓값이 $A_i$가 된다. 그러한 구간의 개수는 $(i-s_i)(e_i-i)+e_i-s_i+1$이다. 즉 최댓값의 총 합은 $A_i \times ((i-s_i)(e_i-i)+e_i-s_i+1)$의 총 합이다.

$s_i$, $e_i$는 스택으로 쉽게 구할 수 있다. (boj 17298 오큰수)

최솟값에 대해서도 똑같이 하면 되는데, 이때 그냥 모든 수의 부호를 뒤집어서 정확히 똑같은 과정을 진행시키면 된다.

Code