Codeforces Round #553 (Div. 2) E 贡献

https://codeforces.com/contest/1151/problem/E

题意

一条长n的链,每个点上有值\(a[i]\),定义\(f(l,r)\)为该区间的\(值\)所代表的点留下来后的联通块数量,求\(\sum^n_{l=1} \sum^n_{r=1} f(l,r)\)

题解

• 计算贡献,计算每个点留下后作为联通块的第一个点的情况数就是这个点的贡献

代码

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll n,a[100005],ans,r;

int main(){

	cin>>n;

	for(int i=1;i<=n;i++){

		scanf("%lld",&a[i]);

		if(a[i]>a[i-1]){

			r=n;

			ans+=(r-a[i]+1)*(a[i]-a[i-1]);

		}else if(a[i]<a[i-1]){

			r=a[i-1]-1;

			ans+=(a[i])*(a[i-1]-a[i]);

		}

		//cout<<ans<<endl;

	}

	cout<<ans;

}