【CF1151E】Number of Components

题面

CF

题解

联通块个数=点数-边数。

然后把边全部挂在较小的权值上。

考虑从小往大枚举左端点，等价于每次删掉一个元素，那么删去点数，加上边数，修改一下当前值就行了。

这个东西对于任意形态的树都可以做。

#include<iostream>

#include<cstdio>

#include<vector>

using namespace std;

#define ll long long

#define MAX 100100

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,a[MAX],b[MAX];ll ans,now;

vector<int> E[MAX];

int main()

{

	n=read();

	for(int i=1;i<=n;++i)a[i]=read(),b[a[i]]+=1;

	for(int i=1,s=0;i<=n;++i)now+=(s+=b[i]);

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

	{

		int u=min(a[i],a[i+1]),v=max(a[i],a[i+1]);

		E[u].push_back(v);now-=n-v+1;

	}

	ans+=now;

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

	{

		now-=1ll*(n-i+1)*b[i];

		for(int v:E[i])now+=n-v+1;

		ans+=now;

	}

	printf("%lld\n",ans);

	return 0;

}