【POJ 2796】【単調スタック】

WAのデータのセット--

10
0 0 0 0 0 0 0 0 0 0

問題は、各数について、それを最小値とする最も遠い左右の端点を求めることに変換されます.
単調スタックの利用:スタックの底が小さく、スタックの頂部が大きい単調スタックを維持する
各数がスタックに入るときに左端点を記録する(スタック内の前の数のシーケンス位置+1)
スタックを出たときに右端を記録する(スタックを出たときの数のシーケンス位置-1)

#include 
#include 
#include 
#include 
#define N 300005
#define LL long long

using namespace std;

inline int wread(){
	char c(getchar ());int wans(0),flag(1);
	while (c'9'){if (c=='-') flag=-1;c=getchar ();}
	while (c>='0' && c<='9'){wans=wans*10+c-'0';c=getchar ();}
	return wans*=flag;
}

int n; 
int sav[N];
struct node{
	int zhi,pos;
	node()
	{}node(int x,int y):zhi(x),pos(y){}
}S[N];
int top;
int ml[N],mr[N];
LL sum[N];

int main (){
	n=wread();
	for (int i(1);i<=n;++i)
		sav[i] = wread();
	for (int i(1);i<=n;++i)
		sum[i] = sum[i-1]+(LL)sav[i];
	S[++top] = node(sav[1],1) ;
	ml[1]=1;
	int r(1);
	while (r!=n){
		r++;
		if (sav[r]>S[top].zhi)	ml[r]=S[top].pos+1,S[++top] = node(sav[r],r);
		else if (sav[r]==S[top].zhi)	ml[r]=ml[S[top].pos],S[++top] = node(sav[r],r);
		else {
			while (S[top].zhi>sav[r] && top>=1)	mr[S[top].pos]=r-1,top--;
			if (!top)	S[++top]=node(sav[r],r),ml[r] = 1;
			else {
				if (S[top].zhi==sav[r])	ml[r] = ml[S[top].pos],S[++top] = node(sav[r],r);
				else ml[r] = S[top].pos +1,S[++top] = node(sav[r],r);
			}
		}
	}
	while (top!=0)	mr[S[top].pos] = n,top--;
	LL ans(-1);int pr(0);
	for (int i(1);i<=n;++i)
		ans < ((LL)sav[i]*( sum[mr[i]] - sum[ml[i]-1] )) ? (pr=i,ans=((LL)sav[i]*( sum[mr[i]] - sum[ml[i]-1] ))) : ans=ans;
	printf("%lld
",ans);
	printf("%d %d
",ml[pr],mr[pr]);
	return 0;
}