51Nod - 1215 数组的宽度 思维+单调栈

题目链接

题意:

N个整数组成的数组，定义子数组aii..ajj的宽度为：max(aii..ajj) - min(aii..ajj)，求所有子数组的宽度和。

思路:

对于这个题目只需要跑一次递增的单调栈,跑一次递减的就可以了.

分别记录以该点为最小值可以到达的左右区间,和为最大值可以到达的左右区间.

 

    因为可以算出,如果该点左侧有x个点,右侧有y个点,（包括该点)，那么经过该点的区间有x*y个.

算出这个就可以ans+=ai*x1*y1,ans-=ai*x2*y2。

  还有就是需要特别注意的就是等号的问题,对于具有相等值的，我们要特别注意重复的计算.

所以这里要么对左端点全加等号,要么对右端点全加等号.即当出现相等情况时规定第一次出现或最后

一次出现的为最值.

举例:  1 1 1 3 3  

#include<bits/stdc++.h>
#define Ri(a) scanf("%d", &a)
#define Rl(a) scanf("%lld", &a)
#define Rf(a) scanf("%lf", &a)
#define Rs(a) scanf("%s", a)
#define Pi(a) printf("%d\n", (a))
#define Pf(a) printf("%lf\n", (a))
#define Pl(a) printf("%lld\n", (a))
#define Ps(a) printf("%s\n", (a))
#define W(a) while(a--)
#define CLR(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define exp 0.00000001
#define  pii  pair<int, int>
#define  mp   make_pair
#define  pb   push_back
using namespace std;
typedef long long ll;
const int maxn=5e5+10;
int n;
ll minl[maxn],minr[maxn],maxr[maxn],maxl[maxn];
ll a[maxn];
stack<int>st,s;
void _clear1()
{
	while(!st.empty())
	st.pop();
	return ;
}
void _clear2()
{
	while(!s.empty())
	s.pop();
	return ;
}
int main()
{
	Ri(n);
	for(int i=1;i<=n;i++)
	Rl(a[i]);
	_clear1();
	_clear2();
	//minl[1]=maxl[1]=1;
//	minr[n]=maxr[n]=n;
	for(int i=1;i<=n;i++)
	{
		if(st.empty())
		{
			minl[i]=1;
			st.push(i);
		}
		else
		{
			if(a[st.top()]>a[i])
			{
				while(!st.empty()&&a[st.top()]>a[i])
				{
					st.pop();
				}
				if(st.empty())
				minl[i]=1;
				else
				minl[i]=st.top()+1;
				st.push(i);
			}
			else
			{
				minl[i]=i;
				st.push(i);
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(s.empty())
		{
			maxl[i]=1;
			s.push(i);
		}
		else
		{
			if(a[s.top()]<a[i])
			{
				while(!s.empty()&&a[s.top()]<a[i])
				{
					s.pop();
				}
				if(s.empty())
				maxl[i]=1;
				else
				maxl[i]=s.top()+1;
				s.push(i);
			}
			else
			{
				maxl[i]=i;
				s.push(i);
			}
		}
	}
	_clear1();
	_clear2();
	for(int i=n;i>=1;i--)
	{
		if(st.empty())
		{
			minr[i]=n;
			st.push(i);
		}
		else
		{
			if(a[st.top()]>=a[i])
			{
				while(!st.empty()&&a[st.top()]>=a[i])
				{
					st.pop();
				}
				if(st.empty())
				minr[i]=n;
				else
				minr[i]=st.top()-1;
				st.push(i);
			}
			else
			{
				minr[i]=i;
				st.push(i);
			}
		}
	}
	for(int i=n;i>=1;i--)
	{
		if(s.empty())
		{
			maxr[i]=n;
			s.push(i);
		}
		else
		{
			if(a[s.top()]<=a[i])
			{
				while(!s.empty()&&a[s.top()]<=a[i])
				{
					s.pop();
				}
				if(s.empty())
				maxr[i]=n;
				else
				maxr[i]=s.top()-1;
				s.push(i);
			}
			else
			{
				maxr[i]=i;
				s.push(i);
			}
		}
	}
	ll ans1=0,ans2=0;
	for(int i=1;i<=n;i++)
	{
		ans1+=(ll)(i-maxl[i]+1)*(maxr[i]-i+1)*(ll)a[i];
		ans2+=(ll)(i-minl[i]+1)*(minr[i]-i+1)*(ll)a[i];
		printf("%lld %lld %lld %lld\n",minl[i],minr[i],maxl[i],maxr[i]);
	}
	Pl(ans1-ans2);
 return 0;
}