[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;
}