[CF1151E] Number of Components

[CF1151E] Number of Components - 组合

Description

有一条 (n(1 leq n leq 10^5)) 个节点的链，编号相邻节点有边，每个点一个权值 (a_i(1 leq a_i leq n))，(f(l,r)) 定义为权值在 ([l,r]) 的点中的连通块数量求 (sum_{l=1}^{n}sum_{r=l}^{n}f(l,r))

Solution

将连通块转化为点数-边数，分别处理

点数：每个点被算 (x(n-x+1)) 次

边数：边 (x,y) 被算 (min(x,y) cdot (n-max(x,y)+1)) 次

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

signed main()
{
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<int> a(n + 2);

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int ans = 0;

    for (int i = 1; i <= n; i++)
    {
        ans += a[i] * (n - a[i] + 1);
        if (i < n)
            ans -= min(a[i], a[i + 1]) * (n - max(a[i], a[i + 1]) + 1);
    }

    cout << ans << endl;
}