백준27471 시그마 시그마 시그마 시그마

작성일 | In

문제 링크

  • https://icpc.me/27471

사용 알고리즘

  • 세그먼트 트리

시간복잡도

  • $O(N \log N)$

풀이

시그마가 4개 중첩되어 있지만 별로 복잡하지 않습니다. 길이가 2 이상인 모든 연속한 부분 수열에서, 가능한 모든 원소 쌍에 대해 둘 중 최댓값을 더하는 문제입니다. 즉, $A$의 연속한 부분 수열 $A[l\cdots r]$에서, 모든 $l \leq i < j \ leq r$에 대해 $\max(A_i, A_j)$의 합을 구하는 문제입니다.

$A_i = A_j$인 경우를 처리하는 것이 귀찮을 것 같으니 수를 비교하는 대신 순서쌍 $(A_i, i)$와 $(A_j, j)$를 비교합시다. 이렇게 하면 값이 같더라도 최대가 되는 원소를 항상 일정한 방향으로 고정할 수 있습니다.

더블 카운팅과 비슷한 느낌으로 $A_i$가 최대가 되는 경우의 수를 구합시다. $A_i$의 왼쪽에서 $A_i$ 이하인 값의 개수, 그리고 $A_i$의 오른쪽에 있으면서 $A_i$ 미만인 값의 개수를 구하면 됩니다. 세그먼트 트리를 이용해 $O(N \log N)$ 시간에 계산할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int SZ = 1 << 19;
constexpr ll MOD = 998244353;

struct Tree{
    ll T[SZ<<1];
    void update(int x, ll v){
        x |= SZ; T[x] = v % MOD;
        while(x >>= 1) T[x] = (T[x<<1] + T[x<<1|1]) % MOD;
    }
    ll query(int l, int r){
        l |= SZ; r |= SZ; ll res = 0;
        while(l <= r){
            if(l & 1) res = (res + T[l++]) % MOD;
            if(~r & 1) res = (res + T[r--]) % MOD;
            l >>= 1; r >>= 1;
        }
        return res;
    }
} T1, T2;

ll N, A[303030], R;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i], T1.update(i, i), T2.update(i, N-i+1);

    vector<pair<ll,ll>> V;
    for(int i=1; i<=N; i++) V.emplace_back(A[i], i);
    sort(V.begin(), V.end(), greater<>());

    for(auto [v,i] : V){
        T1.update(i, 0); T2.update(i, 0);
        R += T1.query(1, i-1) * v % MOD * (N-i+1) % MOD;
        R += T2.query(i+1, N) * v % MOD * i % MOD;
        R %= MOD;
    }
    cout << R;
}