The Preliminary Contect for ICPC China Nanchang National Invitational I、Max answer【単調なスタック+プレフィックスと+RMQ】

The Preliminary Contect for ICPC China Nanchang National Invitational
I、Max answer
 

 30000 ms

 262144 K

Alice has a magic array.She suggaests that the value of a interval is equal to the sum of the values in the interval,multilied by the smalue in the interval.
Now she is planing to find the max value of the intervals in hearray.Can you help her?
Input
First line contains an integer n(1≦n≦5×10^5).
Second line contains nn integers represent the array a(−10^5≦ai≦10^5)
Output
One line contains an integer represent the answer of the array.
サンプル入力

5
1 2 3 4 5

サンプル出力

36

題意
区間の最小値は区間と最大値です.区間要素はマイナスの可能性があります.
考え方
単調なスタック＋RMQは、ある要素を最小値とする最大区間を単調なスタックを使用して決定し、STテーブルを使用してプレフィックスとの最大、最小値を維持する.
番号Mの要素を最小要素として左に右に拡張できる最大区間を[L,R]とします. 
 
要素が0以上の場合、この要素を含む最大区間を区間内で探します. 
すなわち、[M,R]の最大値-[L-1,M-1]の最小値です. 
 
要素が0より小さい場合、この要素を含む最小区間を区間内で探します. 
 すなわち[M,R]の最小値-[L-1,M-1]の最大値です. 
C++コード

#include
#include
#include

using namespace std;

typedef long long ll;

const int N=500050;

int a[N],s[N],l[N];
ll sum[N],dpmax[N][25],dpmin[N][25];

void ST(int n)
{
	for(int i=0;i<=n;i++) dpmax[i][0]=sum[i],dpmin[i][0]=sum[i];
	for(int j=1;(1<0&&a[s[top]]>a[i])
			{
				ll temp;
				int L=l[s[top]],M=s[top],R=i-1;
				if(a[M]>=0)
				  temp=query(M,R,0)-query(L-1,M-1,1);
				else
				  temp=query(M,R,1)-query(L-1,M-1,0);			
				ans=max(ans,temp*a[M]);//     
				l[i]=l[s[top]];
				top--;
			}
			if(top>0&&a[s[top]]==a[i]) l[i]=l[s[top]];
			s[++top]=i;
		}
		printf("%lld
",ans); 
	}
	return 0;
}