博客

c++代码

子串的最大差

定义序列的最大差为序列中最大数与最小数的差。比如 (3,1,4,5,6)(3,1,4,5,6) 的最大差为 6−1=56−1=5 , (2,2)(2,2) 的最大差为 2−2=02−2=0 。

定义一个序列的子串为该序列中连续的一段序列。

给定一个长度为 nn 的数组 a1,a2,…,ana1,a2,…,an，请求出这个序列的所有子串的最大差之和。

输入格式

第一行一个数字 nn。

接下来一行 nn 个整数 a1,a2,…,ana1,a2,…,an。

输出格式

一个数，表示答案。

样例输入

3
1 2 3

样例输出

4

数据规模

所有数据保证 1≤n≤500000,0≤ai≤1081≤n≤500000,0≤ai≤108。

#include<bits/stdc++.h>
using namespace std;
long long n,a[500001],lmax[500001],lmin[500001],rmax[500001],rmin[500001];
stack <int> lx,ld,rx,rd;
long long ans;
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	 } 
	 for(int i=1;i<=n;i++)
	 {
		//a[i]为min的左边界
	 	while(!lx.empty())
		 {
		 	if(a[lx.top()]>=a[i]) lx.pop();
		 	else break;
		  } 
	 	if(lx.empty())lmin[i]=0;else lmin[i]=lx.top();
	 	lx.push(i);
		
	 	//a[i]为max的左边界
	 	while(!ld.empty())
		 {
		 	if(a[ld.top()]<=a[i]) ld.pop();
		 	else break;
		  } 
	 	if(ld.empty())lmax[i]=0;else lmax[i]=ld.top();
	 	ld.push(i);
	 }
	 for(int i=n;i>=1;i--)
	 {
		//a[i]为min的you边界
		while(!rx.empty())
		 {
		 	if(a[rx.top()]>a[i]) rx.pop();
		 	else break;
		  } 
	 	if(rx.empty())rmin[i]=n+1; else rmin[i]=rx.top();
	 	rx.push(i);
		
		//a[i]为max的you边界
		while(!rd.empty())
		 {
		 	if(a[rd.top()]<a[i]) rd.pop();
		 	else break;
		  } 
	 	if(rd.empty())rmax[i]=n+1; else rmax[i]=rd.top();
	 	rd.push(i);
	 }
	 
	ans=0;
    for(long long i=1;i<=n;i++)
    {
    	ans+=((i-lmax[i])*(rmax[i]-i)-(i-lmin[i])*(rmin[i]-i))*a[i];
	}
	cout<<ans;
	return 0;
 }