BOJ 2867 수열의 값

수열의 값
(http://boj.kr/2867)

 

최댓값과 최솟값은 별개다. 즉, 모든 부분수열에서 최댓값의 합 - 최솟값의 합을 구하면 되는 문제다.

주어진 수열을 \(a\)라고 하자. 그리고 현재 보고 있는게 \(i\)번쨰 항이라는건 \(i\)번째 항으로 끝나는 부분수열만 보겠다는 뜻이라고 하자.

우선 최댓값과 최솟값은 같은 방법으로 구할 수 있을테니 최댓값만 생각해보자.
\(a_i\)가 \(1\sim i\)번째 항까지의 최댓값이라고 해보자. 그렇다면 \(a_i\)로 끝나는 부분수열은 항상 \(a_i\)가 최댓값일 수밖에 없다.
\(a_{i-2}\)가 \(1\sim i\)번째 항까지의 최댓값이고, \(a_i\)가 그 이후의 최댓값이라고 해보자. 그렇다면 \(a_i\)로 끝나는 부분수열 중 \(i-2\)개는 \(a_{i-2}\)가 최댓값이고 2개는 \(a_i\)가 최댓값이다.

그래서 최댓값을 내림차순 스택으로 관리할 수 있다. 스택이 내림차순으로 되도록 원소를 넣으면서, \(a_i\)가 최댓값인 경우가 몇 번 있는지를 따로 계산해주면 된다. 뺄 때는 더해졌던만큼 다시 계산하면 된다.

마찬가지로 최솟값은 오름차순 스택으로 관리해서 \(a_i\)로 끝나는 부분수열의 최댓값 - 최솟값을 \(O(n/n)\)만에 구할 수 있다.

#include <bits/stdc++.h>
 
using namespace std;
 
long long arr[300000], stk1tot, stk2tot;
int stk1[300001], stk2[300001], e1, e2;
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0;i < n;++i)
        scanf("%lld", &arr[i]);
 
    long long ans = 0;
    stk1[e1++] = -1;
    stk1[e1++] = 0;
    stk1tot += arr[0];
    stk2[e2++] = -1;
    stk2[e2++] = 0;
    stk2tot += arr[0];
    for (int i = 1;i < n;++i) {
        stk1tot += mntot;
        while (e1 - 2 >= 0 && arr[stk1[e1 - 1]] > arr[i]) {
            stk1tot -= (stk1[e1 - 1] - stk1[e1 - 2]) * arr[stk1[e1 - 1]];
            e1--;
        }
        stk1tot += (i - stk1[e1 - 1]) * arr[i];
        stk1[e1++] = i;
        stk2tot += mxtot;
        while (e2 - 2 >= 0 && arr[stk2[e2 - 1]] < arr[i]) {
            stk2tot -= (stk2[e2 - 1] - stk2[e2 - 2]) * arr[stk2[e2 - 1]];
            e2--;
        }
        stk2tot += (i - stk2[e2 - 1]) * arr[i];
        stk2[e2++] = i;
 
        ans -= stk1tot;
        ans += stk2tot;
    }
 
    printf("%lld", ans);
 
    return 0;
}