题解 CF1151E 【Number of Components】

2019-04-20 08:44:21


应该是我AC的1000 题,发篇题解祭

另外这场也让我的CF$\color{purple}{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;
 }