【图论】【寻找性质】CF1151E Number of Components 题解

CF1151E

发现每一个 \(f(l, r)\) 中的连通块总是一条链（一棵树）。

那么此时连通块的数量就等于点的数量减去边的数量。

先考虑点的总数，一个价值为 \(a_i\) 的点一定是在 \(l \leqslant a_i\) 且 \(r\geqslant a_i\) 的 \(f(l, r)\) 中才会有一个贡献，根据乘法原理，它会产生 \(a_i\times (n - a_i + 1)\) 的贡献。

再考虑边的总数，因为边是从 \(i\) 连向 \(i + 1\) 的，当且仅当 \(l\leqslant \min(a_i, a_{i + 1})\) 且 \(r\geqslant \max(a_i, a_{i + 1})\) 时，这条边才会有一个贡献，根据乘法原理，它会产生 \(\min(a_i, a_{i + 1})\times (n - \max(a_i,a_{i + 1}) + 1)\) 的贡献。

最后答案就显而易见了。

时间复杂度：\(\mathcal{O}(n)\)

代码：

const int N = 1e5 + 5;
int n, a[N];

int main() {
	n = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	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 << endl;
	return 0;
}