BOJ 25490 수열의 점수

왼쪽에서부터 원소를 하나씩 추가해가면서, $i$번째 iteration에 $\sum_{j=1}^{i} \min(v[j..i]) \max(v[j..i])$를 빠르게 구하는 방법이 존재합니다.

다음과 같이 레이지 세그먼트 트리를 정의합니다.

• 데이터: (구간의 길이, 구간 내에서 각 시작점에서 현재 끝점까지의 구간들의 $\min$들의 합, $\max$들의 합, $\min \times \max$들의 합)
• 레이지 함수: (구간의 모든 $\min$을 $x$로 변경 또는 아무것도 하지 않음, 구간의 모든 $\max$를 $y$로 변경 또는 아무것도 하지 않음)
• 두 데이터를 합치는 연산: 네 값들을 각각 더함
• 레이지 함수 합성: 각각 마지막 업데이트 값으로 변경
• 데이터에 함수 적용: 값 변경이 있을 경우 구간 전체가 같은 값으로 변경되므로 적절한 곱을 이용하여 네 개의 값을 모두 구할 수 있습니다.

이제 각각의 원소에 대해 업데이트 방법과 구간을 찾아야 합니다. 이는 다음과 같이 해결할 수 있습니다.

• $v[i-1]$과 $v[i]$를 비교합니다. $v[i-1] = v[i]$라면 기존의 $\min$과 $\max$ 중에서 아무것도 바뀌지 않습니다.
• $v[i-1] < v[i]$라면, $\max$를 업데이트할 구간을 찾습니다. $\max$는 단조감소하므로 업데이트 구간의 왼쪽 끝점을 점 쿼리를 통한 이분 탐색으로 구할 수 있습니다.
• $v[i-1] > v[i]$라면 $\min$을 업데이트할 구간을 같은 방법으로 찾을 수 있습니다.

새로운 원소는 그 칸에 레이지 함수 $(v[i], v[i])$를 적용하는 것으로 추가할 수 있습니다.

이제 $i = 1..n$에 대해 위의 과정을 루프를 돌면서 전체 쿼리 결과를 모두 더해서 출력하면 됩니다. 모듈로 처리에 주의합니다.