51nod1215 数组的宽度

傻叉单调栈

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

using namespace std;

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define clr(x,c) memset(x,c,sizeof(x))

#define ll long long

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int nmax=5e4+5;

const int inf=0x7f7f7f7f;

int a[nmax],q[nmax],l[nmax],R[nmax],tl[nmax],tr[nmax];

int main(){

	int n=read(),u,v,d,tmp,temp;

	rep(i,1,n) a[i]=read();

	int r=0;

	rep(i,1,n){

		while(r&&a[q[r]]>a[i]) --r;

		l[i]=q[r]+1;q[++r]=i;

	}

	r=0;q[0]=n+1;

	dwn(i,n,1){

		while(r&&a[q[r]]>=a[i]) --r;

		R[i]=q[r]-1;q[++r]=i;

	}

	r=0;q[0]=0;

	rep(i,1,n){

		while(r&&a[q[r]]<a[i]) --r;

		tl[i]=q[r]+1;q[++r]=i;

	}

	r=0;q[0]=n+1;

	dwn(i,n,1){

		while(r&&a[q[r]]<=a[i]) --r;

		tr[i]=q[r]-1;q[++r]=i;

	}

	ll ans=0;

	rep(i,1,n) ans+=(ll)(tr[i]-i+1)*(i-tl[i]+1)*a[i]-a[i];

	rep(i,1,n) ans-=(ll)(R[i]-i+1)*(i-l[i]+1)*a[i]-a[i];

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

	return 0;

}

1215 数组的宽度 51nod1215 数组的宽度

题目来源： Javaman

基准时间限制：1 秒空间限制：131072 KB 分值: 80 难度：5级算法题

关注

N个整数组成的数组，定义子数组a[i]..a[j]的宽度为：max(a[i]..a[j]) - min(a[i]..a[j])，求所有子数组的宽度和。

Input

第1行：1个数N，表示数组的长度。(1 <= N <= 50000)

第2 - N + 1行：每行1个数，表示数组中的元素(1 <= A[i] <= 50000)

Output

输出所有子数组的宽度和。

Input示例

Output示例

秒客网

51nod1215 数组的宽度

相关文章