一、单调栈

定义：

单调栈，顾名思义就是说栈内的元素，按照某种方式排序下，必须是单调的。如果新入栈的元素破坏了单调性，就弹出栈内元素，知道满足单调性。它可以很方便地求出某个数的左边或者右边第一个比它大或者小的元素，而且总时间复杂度O(N)。
　　
向右看齐Look Up
模板题
AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int a[maxn],sta[maxn],query[maxn];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    int beg=1;///beg表示栈中元素个数
    sta[beg]=1;///第一个元素的下标入栈
    for(int i=2;i<=n;i++){
    while(a[i]>a[sta[beg]]&&beg!=0){//栈要非空且新入栈的元素要符合单调性
        query[sta[beg]]=i;///记录某个数的左边或者右边第一个比它大或者小的元素
        beg--;///出栈
    }
    sta[++beg]=i;///入栈
    }
    for(int i=1;i<=n;i++){
    printf("%d\n",query[i]);
    }
    return 0;
}

加入快读代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int a[maxn],sta[maxn],query[maxn];
int re()//快读
{
    int x=0;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=x*10+(c-'0');
    return x;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    a[i]=re();
    int beg=1;
    sta[beg]=1;
    for(int i=2;i<=n;i++){
    while(a[i]>a[sta[beg]]&&beg!=0){
        query[sta[beg]]=i;
        beg--;
    }
    sta[++beg]=i;
    }
    for(int i=1;i<=n;i++){
    printf("%d\n",query[i]);
    }
    return 0;
}

Bad Hair Day
思路
构造一个严格单调递减的单调栈，然后让n个元素依次入栈然后出栈，出栈与入栈的时间差就是该元素的c值。所以为了让所有元素出栈就把第n+1个元素设为1e9+5;

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=8e4+5;
typedef long long ll;
int a[maxn],sta[maxn];
template <class T>
inline int read(T &ret){
	char c;int sgn;
	if(c=getchar(),c==EOF) return 0;
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c==' ')?-1:1;
	ret=(c==' ')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}//快读把时间从150ms缩短成19ms;
int main(){
    int n;
    ll sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
	read(a[i]);
    int beg=1;
    sta[beg]=1;
    a[n+1]=1e9+5;
    for(int i=2;i<=n+1;i++){
	while(a[i]>=a[sta[beg]]&&beg!=0) {
		sum+=i-sta[beg]-1;
		beg--;
	}
	sta[++beg]=i;
    }
    printf("%lld\n",sum);
    return 0;
}

**
定理：单调栈可以解决在一串数列中，任意元素最左与最右延长深度问题
问题：设由a1,a2,a3,…,an组成的数列，求ai (i属于[1,n])的最大区间[l,r] （使得区间[l,r]中的所有元素都不小于a[i]）
按照普通模拟，复杂度是O（N）。但是使用单调栈的话,复杂度仅有O（n）.
往右扫一遍可以得到每一个元素最大区间的 l;
往左扫一遍可以得到每一个元素最大区间的 r;
证明
假设 a[j] 的最大区间的 l 已经求出，那么对于 j+1 的最大区间的 l 怎么求呢？
如果 a[j+1]>a[j],显然最大区间的 l 就是 j+1。
如果 a[j+1]<=a[j] , 设 a[j] 的最大区间的 l 为 J；那么 [J,j] 里面的元素值均>=a[j]>=a[j+1] ，所以 a[j+1] 的最大区间的 l<=J;直到
a[j+1]>a[m],那么 a[j+1]的最大区间的 l 更新结束。

求r的原理与上面类似，再次不加以赘述。

了解这个定理之后，可以尝试解决这道Feel Good

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef struct P{
	ll val;
	int l,r;
};
const int maxn=1e5+5;
ll sum[maxn],sta[maxn],stb[maxn];
P a[maxn];
int main(){
    ll ans=0;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
	scanf("%lld",&a[i].val);
	a[i].l=a[i].r=i;
	sum[i]=sum[i-1]+a[i].val;
    }///前缀和求各区间的值
    int beg=1;
    sta[beg]=1;
    for(int i=2;i<=n;i++){
	while(beg!=0&&a[sta[beg]].val>=a[i].val){
		a[i].l=a[sta[beg]].l;
		beg--;
	}
	sta[++beg]=i;
    }///最大区间的左值求出
    int st=1;
    stb[st]=n;
    for(int i=n-1;i>=1;i--){
	while(st!=0&&a[stb[st]].val>=a[i].val){
		a[i].r=a[stb[st]].r;
		st--;
	}
	stb[++st]=i;
    }///最大区间的右值求出
    int left,right;
    for(int i=1;i<=n;i++){
	ll tmp=(sum[a[i].r]-sum[a[i].l]+a[a[i].l].val)*a[i].val;
	ans=max(ans,tmp);
	if(ans==tmp){
		left=a[i].l;
		right=a[i].r;
	}
    }
    printf("%lld\n%d %d\n",ans,left,right);
    return 0;
}