Codeforces 1151E (简单图连通块转化)

Codeforces 1151E
题意：求
$$
\sum_{i=1}^n\sum_{j=i}^nf(i,j)
$$
其中$f(i,j)$表示只保留权值在$[i,j]$之间的点形成的连通块数量。

一看连通块，就考虑转化，连通块数量=点数-边数。
然后考虑每个点和每条边对答案的贡献，用点个数减掉边个数即可。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    int n, a[100000 + 5];

    void clean() {}
    int solve() {

        clean();
        cin >> n;
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        LL ans = 0;
        for (int i = 1; i <= n; ++i) ans += 1ll * a[i] * (n - a[i] + 1);
        for (int i = 1; i < n; ++i) {
            ans -= 1ll * min(a[i], a[i + 1]) * (n - max(a[i], a[i + 1]) + 1);
        }
        cout << ans;

        return 0;
    }  
}
int main() {
    flyinthesky::solve();
    return 0;
}