单调栈

POJ 2796

题目的大致意思是，给你n个数，我们需要计算一个值，这个值是这个序列中的一段连续的子序列里的最小值乘于这段连续子序列的和，我们要使得求得的这个值最大，比如样例 6 3 1 6 4 5 2，我们选择6 4 5这段连续的子序列，值为4*(6+4+5)=60
首先对于每个数a[i]，我们想让他最大可能的往左右扩展，知道这个数往左和往右最大的扩展的坐标l,r,利用前缀和我们就求得了这个值a[i]*(s[r]-s[l-1])，所以这题在于我们怎么去求一个数往左右扩展的最大位置.
我们先以往右扩展为例，用 R[i] 表示 i 往右扩展的最大位置。我们建立一个单调栈，这个单调栈是单调递减的，即栈顶到栈底递减，用数组表示即是从左到右递增。我们扫描这个序列。

• 如果当前这个数比栈顶大或者等于，我们直接入栈。
• 如果当前这个数比栈顶小，我们就从栈中弹出数，直到这个数比栈顶大，那怎么记录往右扩展的最大位置呢，我们在把数从栈中弹出的过程中，弹出的数一定比当前要入栈的数大，因此他一定不是最小的数，对后面没有作用，因此弹出的数最大扩展位置就是当前这个数的位置i再减去1,即i-1。
  我们用pos数组记录一下栈中数所在的位置，同时a[n+1]设为-1，保证最后栈中元素都可以被弹出。
  向左扩展也是一样道理。

#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int a[N], n, L[N], R[N], s[N], tot, pos[N];
ll sum[N];
pair<int, int> ans;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        sum[i] = sum[i - 1] + 1LL*a[i];
        L[i] = R[i] = i;
    }
    a[n + 1] = -1;
    for (int i = 1; i <= n+1; i++)
    {
        if (a[i] >= s[tot])
            s[++tot] = a[i],pos[tot]=i;
        else{
            while (tot&&a[i] < s[tot]){
                R[pos[tot]] = i - 1;
                tot--;
            }
            s[++tot] = a[i],pos[tot]=i;
        }
    }
    a[0] = -1,tot=0;
    for (int i = n; i >= 0; i--){
        if (a[i] >= s[tot]){
            s[++tot] = a[i],pos[tot]=i;
        }
        else{
            while (tot&& a[i] < s[tot]){
                L[pos[tot]] = i+1;
                tot--;
            }
            s[++tot] = a[i], pos[tot] = i;
        }
    }
    ll max_val= -1;
    for (int i = 1; i <= n; i++){
        if (a[i]*(sum[R[i]] - sum[L[i] - 1]) > max_val)
        {
            max_val = a[i] * (sum[R[i]] - sum[L[i] - 1]);
            ans.first = L[i];
            ans.second = R[i];
        }
    }
    cout << max_val << endl;
    cout << ans.first << " " << ans.second << endl;
    return 0;
}