Editorial

---

D2

summary:

$a_l \dots a_r$구간을 정렬하는데 $r-l$ 비용이 든다.

모든 $(l,r)(0\leq l<r < n)$ 구간을 정렬하는 비용의 최솟값의 합을 구하는 문제이다.

description:

$max(a_l\dots a_k)<min(a_{k+1} \dots a_r)$인 경우에

$a_l \dots a_r$을 $a_l \dots a_k$ , $a_{k+1} \dots a_r$의 두개의 구간으로 나누어서 따로 정렬 시킬수 있고, 나누지 않고 $(l,r)$구간을 정렬할 때보다 비용을 1 감소 시킬수 있다.

모든 인덱스 $i$에 대해, $min(a_{k+1} \dots a_r)=a_i$로 고정하고 위 조건에 맞는 (l,k,r)의 개수의 최댓값을 구하자.

$min(a_{k+1} \dots a_r)=a_i$이기 때문에

$r$의 최댓값: $a_y < a_i(i<y)$를 만족하는 $y$의 최솟값-1 이다.

$max(a_l\dots a_k)<min(a_{k+1} \dots a_r)$이기 때문에

$k$의 최댓값: $a_k<a_i(k<i)$를 만족하는 $k$의 최댓값이다.

$l$의 최솟값: $a_x>a_i(x<i)$를 만족하는 $x$의 최댓값+1이다.

즉 $x<l<=k,i<=r<y$이기 때문에 $min(a_{k+1} \dots a_r)=a_i$일때 감소시킬수 있는 비용의 최댓값은 $(y-i)*(k-x)$이 된다.

모든 가능한 구간을 나누지 않고 정렬했을 경우 비용은 $1(n-1)+2(n-2)+3(n-3)+\dots+(n-1)1$ 이 되고, 여기서 모든 $i$에 대해 구한 감소시키는 값들의 합을 빼주면 된다.