Codeforces 553 DIV2 E. Number of Components (R2100)

面白かった。

• 「全体についての総和についての総和」を「個別の要素についての総和を各要素について総和」とするテク
• 区間の連結成分の個数は、各隙間に左端が入り込むかを数える

という典型テクが詰まった問題。

問題へのリンク

問題概要

要素からなる数列 があって、各要素の値は 以上 以下の整数である。 に対して

• := 数列から 以上 以下のものだけを残したときに残る連続する区間の個数

としたときの、 についての の総和を求めよ。

制約

• 

考えたこと

この手の問題は、個別の要素に着目すると相場は決まっている。そして連続する区間の個数の数え上げは

• 数列の各隙間について、そこが区間の左端になっている場合に 1 を足して、そうでない場合に 0 を足す

という風に考えられることも典型！！！
あとは頑張る。

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<int> a;

long long solve() {
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        // i-1, i の隙間が何回左端としてぶった切られるか
        int prev = (i == 0 ? 0 : a[i-1]);
        int cur = a[i];
        long long left = (prev <= cur ? cur - prev : cur);
        long long right = (prev >= cur ? prev - cur : N - cur + 1);
        long long add = left * right;
        res += add;
   }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    while (cin >> N) {
        a.resize(N);
        for (int i = 0; i < N; ++i) cin >> a[i];
        cout << solve() << endl;
    }
}