题解 CF1151E 【Number of Components】

应该是我AC的1000 题，发篇题解祭 另外这场也让我的CF[$\color{purple}{Ynoi}$](https://codeforc.es/profile/Ynoi)紫名了 这场其实先开DE的是很赚的，因为其实都不难 闲话不多说，我说一下思路： 考虑每个点的贡献 我们认为一个联通块里让编号最大的点产生贡献 那么，对于一个点i，我们考虑她如果要对答案产生贡献，一定要点 i 存在，而点i + 1 不存在 而点n只用包含这个点就行了 这样我们求出每个点符合条件的区间个数即可 具体是这样子的 如果$a_i > a_{i+1}$ 贡献 = $(a_i - a_{i+1})*(n-a_i+1)$ 如果 $a_i < a_{i+1}$ 贡献 = $(a_{i+1}-a_i)*a_i$ ``` #include<bits/stdc++.h> using namespace std; #define int long long #define LL long long #define INF (LL)(0x3f3f3f3f)*(LL)0x3f3f3f3f #define MAXN 100005 LL n,m; LL a[MAXN]; LL ans = 0; signed main() { cin >> n; for(int i = 1; i <= n; i ++) cin >> a[i]; for(int i = 1; i < n; i ++) { int x = a[i],y = a[i+1]; if(x > y) { ans += (x-y)*(n-x+1); } else { ans += (y-x)*x; } } ans += a[n]*(n-a[n]+1); cout<<ans; return 0; } ```