题意

已知一条链，每个节点 $i$ 与节点 $i+1$ 之间有一条边。

每个点有一个点权 $a_i$,$(1\le a_i\le n)$。

定义 $f(l,r)$ 表示只保留点权为 $[l,r]$ 的点，其余点全部删去，所得到的图的联通块个数。

求 $\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$。

题解

考虑分解总和，进行分开求解。

对于一组 $l,r$ ，如果有一个 $i$ 满足 $a_i\in [l,r]$ 且 $a_{i-1}\notin [l,r]$，那么联通块个数加一。

所以枚举每个 $i$ 统计答案即可，时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N];
long long ans;
int main(){
	std::ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		if(a[i]>a[i-1])ans+=1ll*(a[i]-a[i-1])*(n-a[i]+1);
		else ans+=1ll*a[i]*(a[i-1]-a[i]);
	}
	cout<<ans;
}