[COCI 10/11 #3] DIFERENCIJA(수열의 값) ★

문제 링크

질문은 언제나 환영입니다.

 

이 문제는 두 가지 풀이법이 존재합니다.

우선 대표적인 관찰을 확인하고 각 풀이로 전개해 보겠습니다.

 

편의상 주어진 배열은 $A$라고 합시다.

 

관찰. max와 단조성 min의 단조성

배열의 임의의 위치 $k$에 대해 $\max A[i\cdots k]$는 $i$에 대해 단조 감소를 띱니다.

왜냐하면 $i_1<i_2$에 대해 $A[i_1\cdots k]⊊ A[i_2\cdots k]$이기 때문입니다.

 

첫 번째 풀이

여러가지 풀이를 시도해보다가 안 될 때에는 분할 정복도 시도해보기 마련입니다.

길이가 $\ell$인 배열의 가운데 지점 $m$을 기준으로 $m$을 지나는 부분 배열들에 대한 수열의 값을 $O(\ell)$이나 $O(\ell\log \ell)$ 정도에 해결할 수 있을까요?

 

네, 해결할 수 있습니다.

 

다만 그 방법은 조금 복잡한데, 간략하게 소개해보자면...

우선, 배열의 왼쪽 절반에 대해 $m$부터 왼쪽으로 누적 최댓값 배열을 만들고, 누적 최솟값 배열을 만듭니다.

그 다음에는 오른쪽 절반의 각 인덱스에 대해서 $m$부터 오른쪽으로 이동하면서 누적 최댓값 및 최솟값을 관리합니다.

그 다음에는 왼쪽의 누적 최댓값 배열과 누적 최솟값 배열이 단조성을 띤다는 점을 이용해 이진 탐색을 진행합니다.

그렇게 하면 왼쪽 누적 배열은 갱신해야 하는 지점, 원래 값을 그대로 쓰면 되는 지점 등으로 최대 3개의 구간으로 나뉘게 됩니다.

이걸 케이스 분류를 해서 각 경우에 대해 구해주면 됩니다.

 

말이 좀 어려울 것 같은데, 코드를 올려보겠습니다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int N = 300003;
int n;
ll a[N];
ll Lm[N], LM[N];
ll mp[N], Mp[N], dp[N];

void precalc(int x, int m) {
    Lm[m+1] = LM[m+1] = mp[m+1] = Mp[m+1] = dp[m+1] = 0;
    Lm[m] = LM[m] = mp[m] = Mp[m] = a[m];
    dp[m] = 0;
    for (int i = m-1; i >= x; --i) {
        Lm[i] = min(a[i],Lm[i+1]);
        LM[i] = max(a[i],LM[i+1]);
        mp[i] = mp[i+1]+Lm[i];
        Mp[i] = Mp[i+1]+LM[i];
        dp[i] = dp[i+1]+(LM[i]-Lm[i]);
    }
}

int point(ll A[], int x, int y, ll k, bool f(ll,ll)) {
    while (x <= y) {
        int m = (x+y)/2;
        if (f(A[m],k)) y = m-1;
        else x = m+1;
    }
    return x;
}

ll case_work(ll x, ll y, ll p, ll q, ll m, ll M) {
    ll r = 0;
    r += dp[x]-dp[min(p,q)]; // nothing fixed
    if (p <= q) r += (Mp[p]-Mp[q])-(q-p)*m; // m is fixed
    else        r += (p-q)*M-(mp[q]-mp[p]); // M is fixed
    r += (y+1-max(p,q))*(M-m); // M and m are fixed
    return r;
}

ll solve(int x = 1, int y = n) {
    if (x >= y) return 0;
    int m = (x+y)/2;
    ll r = 0;
    // consider ranges s.t. crosses (m+0.5)
    precalc(x,m);
    ll Rmx = a[m+1], Rmn = a[m+1];
    rep(i,m+1,y) {
        Mup(Rmx,a[i]), mup(Rmn,a[i]);
        int p1 = point(Lm,x,m,Rmn,[](ll k, ll l){ return k > l; });
        int p2 = point(LM,x,m,Rmx,[](ll k, ll l){ return k < l; });
        r += case_work(x,m,p1,p2,Rmn,Rmx);
    }
    return r + solve(x,m) + solve(m+1,y);
}

int main() {
    scanf("%d", &n);
    rep(i,1,n) scanf(" %lld ", &a[i]);
    printf("%lld", solve());
}

 

두 번째 풀이

단조 증가/감소를 띨 때에는 단소 스택을 사용하기 마련이죠.

하지만 max와 min을 동시에 관리하려면 머리가 복잡해집니다.

 

따라서 max와 min을 분리하면 좋을 겁니다. 주어진 배열을 $A$라 할 때,

실제로 $\displaystyle \sum_{a\subset A} (\max a-\min a)=\sum_{a\subset A} \max a-\sum_{a\subset A} \min a$으로 바꿔 생각해도 문제가 없을 것입니다.

 

이제 단조 스택을 관리해 봅시다.

 

다음 애니메이션은 배열이 $[3,1,4,2]$일 경우 $k$가 증가함에 따른 $\max a[i\cdots k]$의 최댓값을 관리하는 단조 스택의 변화를 나타냅니다. 이 때 가로축은 $i$입니다.

최댓값을 관리함과 동시에 옆에 적힌 $S$도 함께 관리할 수 있습니다. 그 방법은 스택의 push/pop에 따라 $S$에 변화를 주는 것입니다.

 

그럼 매 $k$마다 $S$를 더해주면 $\displaystyle \sum_{a\subset A} \max a$을 구할 수 있겠네요! 이를 바탕으로 코드를 작성해봅시다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define dbg(x) cerr << #x << ": " << x << '\n'
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int N = 3e5+3;
int n;
ll a[N];

#define V first
#define I second

ll solve(bool cmp(ll,ll)) {
    stack<pair<ll,int>> st;
    ll r = 0, S = 0;
    rep(i,1,n) {
        int s = i;
        while (not empty(st) and cmp(st.top().V,a[i]))
            S -= (s-st.top().I)*st.top().V, mup(s,st.top().I), st.pop();
        st.push({a[i],s});
        r += (S += (i-s+1)*a[i]);
    }
    return r;
}

int main() {
    scanf("%d", &n);
    rep(i,1,n) scanf("%lld", &a[i]);
    auto mx = [](ll x, ll y){return x <= y;};
    auto mn = [](ll x, ll y){return x >= y;};
    printf("%lld", solve(mx)-solve(mn));
}