单调栈 例题:POJ-3250,HDU-1506以及POJ-2796

蒟蒻的第一篇专题……
最近(两天)都在研究单调栈，一开始学单调栈是看这篇文章学的传送门
ps:顺便吐槽一下单调队列那一题，用g++和stdio交会tle，用c++或者用iostream输出都能ac，估计是poj那个老旧的评测机的锅

概述

单调栈是用来干什么的呢？那篇博文讲得不错

单调是一种思想，当我们解决问题的时候发现有许多冗杂无用的状态时，我们可以采用单调思想，用单调队列或类似于单调队列的方法去除冗杂状态，保存我们想要的状态

单调栈和单调队列十分类似，都采用了单调思想来去除一些冗余状态，但我一开始没有搞懂单调栈在实际运用中所起到的作用

菜鸡的假算法(本人反思)

拿POJ3250做例子，一开始我没有完全理解单调栈的时候做了一遍，并且AC了【证明这题题有点水，贴上错误示例

#include<cstdio>

long long h[100011],s[100011],val[100011],top = 0;
long long n,ans = 0;
int main()
{
    scanf("%lld",&n);
    for (int i = 0;i < n;++i)
    {
        scanf("%lld",h + i);
        while (h[i] >= h[s[top]] and top > 0) 
        {
            top--;
            val[top] += val[top + 1];
            ans += val[top + 1];
        }
        val[top]++;
        s[++top] = i;
        val[top] = 0;
    }
    while (top > 0) 
    {
        top--;
        val[top] += val[top + 1];
        ans += val[top + 1];
    }
    printf("%lld",ans);
    return 0;
}

当时我是这样想的……【翻草稿ing
建一个单调递减栈，开一个val数组记录每只牛能看到多少只牛，一个数在入栈之前将原本的栈顶记录的数+1(因为这个数比之前的栈顶小)，在出栈时把自己记录的数给下一层(因为这层能看到的下一层必定能看到)，这里就不放图了
这个假算法对于这一道题确实能过，然而下一题就不一样了……

HDU-1506

这题我一开始是想dp的，但因为刚学单调栈，所以就尝试用单调栈做
但这题用回我的假算法做就不一样了，因为这题比上一题复杂了，错误示范不讲详细过程，最后我推出了一条"状态转移方程"
对于每一个栈:
$ans=max(stack[i]·(id[top]-id[i-1]))$ans=max(stack[i]⋅(id[top]−id[i−1]))

从1到top枚举i

好吧，我相信大佬们一眼就看出来这TLE了，然而可怜的我不太会算时间复杂度
这次错误代码也不贴了

真正的单调栈

经过了一个上午的折腾(期间我改了一下思路，写了个WA的程序，用上述TLE程序对拍，结果把WA程序改对之后也TLE了，也就是花了一个上午时间写了一个我写了10多分钟的程序)，我终于发现单调栈除了单调性之外还有其它的特性,例如数列$\{93,10,40,85,47,19,56\}${93,10,40,85,47,19,56}
模拟一次单调递减栈
先将93和10入栈

top=2	1	2	3	4	5
stack	93	10
id	1	2

将40入栈，发现此时栈顶元素比40小，将10出栈，再将40入栈

top=2	1	2	3	4	5
stack	93	40
id	1	3

将85入栈，同理先将40退栈，后面47，19可以直接入栈

top=4	1	2	3	4	5
stack	93	85	47	19
id	1	4	5	6

最后将56入栈，同理将top减到2再入栈

top=3	1	2	3	4	5
stack	93	85	56
id	1	4	7

这就是整个从左到右的入栈次序了，有一些比较聪明的人可能已经看出id之间的关系，像我这么蠢的人联系一下上面那条式子应该也能想到一些东西
因为出栈的都是比当前栈顶小的数，我们只需要比较一下入栈前的栈顶id和准备进栈的id，也就是$i - id[top] - 1$i−id[top]−1，就能轻松地得到在当前元素左边比其小的元素个数了
知道了这件事，我们只要从左到右扫一遍，再反过来扫一遍，就能知道每一个元素的左右两边一共有多少个比它大(小)的元素了
回到HDU-1506，我们要找到每一个元素左右两边有多少比它大的元素，这样才能以目前元素为高建立一个长方形

#include<cstdio>
#include<cstring>

long long stack[100011],id[100011],h[100011],ans1[100011],ans2[100011],top = 0;

int main()
{
    long long n,ans;
    while (~scanf("%lld",&n) and n != 0)
    {
        ans = 0,top = 0;
        memset(ans1,0,sizeof(ans1));
        memset(ans2,0,sizeof(ans2));
        id[0] = 0;
        for (int i = 1;i <= n;++i)
        {
            scanf("%lld",h + i);
            while (top > 0 and stack[top] >= h[i]) top--;
            ans1[i] = i - id[top];
            stack[++top] = h[i];
            id[top] = i;
        }
        top = 0;
        id[0] = n + 1;
        for (int i = n;i >= 1;--i)
        {
            while (top > 0 and stack[top] >= h[i]) top--;
            ans2[i] = id[top] - i;
            stack[++top] = h[i];
            id[top] = i;
        }
        for (int i = 1;i <= n;++i)
        {
            ans = max(ans,(ans1[i] + ans2[i] - 1) * h[i]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

代码在这了，记住用LL哦
再给出POJ-3250的正解(虽然上面那个也能AC)

#include<cstdio>

long long h[100011],s[100011],top = 0;

long long n,ans = 0;
int main()
{
    scanf("%lld",&n);
    for (int i = 0;i < n;++i)
    {
        scanf("%lld",h + i);
        while (top > 0 and h[i] >= s[top]) top--;
        ans += top;
        s[++top] = h[i];
    }
    printf("%lld",ans);
    return 0;
}

HDU-1506 POJ-3250

练习

POJ-2796 Feel Good
代码在下面(会折叠的大佬教我一下？)
$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$
WA的话……
试试全是0的话会输出什么←反正我被坑了

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$

#include<cstdio>
#define max(a,b) (a > b ? a : b)
long long stack[100011],id[100011],top,l[100011],r[100011],a[100011],sum[100011];
long long ans,al = 1,ar = 1;
int main()
{
    int n;
    scanf("%d",&n);
    top = 0,id[0] = 0,ans = 0;
    for (int i = 1;i <= n;++i)
    {
        scanf("%lld",a + i);
        sum[i] = a[i] + sum[i - 1];
        while (top > 0 and a[i] <= stack[top]) --top;
        l[i] = id[top] + 1;
        stack[++top] = a[i];
        id[top] = i;
    }
    top = 0,id[0] = n + 1;
    for (int i = n;i >= 1;--i)
    {
        while (top > 0 and a[i] <= stack[top]) --top;
        r[i] = id[top] - 1;
        stack[++top] = a[i];
        id[top] = i;
    }
    for (int i = 1;i <= n;++i)
    {
        long long tot = a[i] * (sum[r[i]] - sum[l[i] - 1]);
        if (tot > ans)
        {
            ans = tot;
            al = l[i],ar = r[i];
        }
    }
    printf("%lld\n%lld %lld",ans,al,ar);
    return 0;
}