Codeforces ECR #023 : D. Imbalanced Array

EもFも手を抜きすぎ。
http://codeforces.com/contest/817/problem/D

問題

N要素の数列Aがある。
このうち連続する部分列をBとしたとき、その部分列の不均衡度合とは最大要素と最小要素の差とする。
全連続部分列における不均衡度合の差を求めよ。

解法

あるA[y]に対しA[x]≧A[y]となるy未満で最大のxと、A[y]＜A[z]となるy以上で最小のzを考える。
BにおいてA[y]が最大となるのは、部分列がA[x]およびA[z]を含まずA[y]を含むケースなので(y-x)*(z-y)通りとなる。
xおよびzはスタックを使い配列を両端から操作することで求められる。

同様に最小となるケースの場合の数を求めていけばよい。
A全体を正負反転すると、最大要素と同じ手順で求めることができて楽。

int N;
ll A[1010101];
int L[1010101],R[1010101];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	FOR(i,N) scanf("%d",&A[i]);
	
	ll ret=0;
	
	FOR(j,2) {
		vector<pair<int,int>> V;
		V.push_back({-1,1<<30});
		FOR(i,N) {
			while(V.back().second<=A[i]) V.pop_back();
			L[i]=V.back().first;
			V.push_back({i,A[i]});
		}
		V.clear();
		V.push_back({N,1<<30});
		for(i=N-1;i>=0;i--) {
			while(V.back().second<A[i]) V.pop_back();
			R[i]=V.back().first;
			V.push_back({i,A[i]});
		}
		FOR(i,N) ret+=A[i]*(R[i]-i)*(i-L[i]);
		
		FOR(i,N) A[i]=-A[i];
	}
	cout<<ret<<endl;
	
	
}

まとめ

まぁこれは問題なし。