发现单调栈的题目基本不会做

做几道简单题找感觉

题意：

给定$n\le100000$的数列${a_n}$，求使
$$
ans=\min_{l\le i\le r}{a[i]}*\sum_{i=l}^{r}a[i]
$$
最大的区间以及其$ans$

考虑对于每一个$a[i]$,以其为$\min$的最大$ans$区间必为向左向右延伸的最大区间

那么可以用单调栈做两遍，第一遍求出向左延伸的最远点，第二遍求向右的

最后统计答案即可

复杂度$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//by Richard
#include <cstdio>
#include <iostream>
#include <stack>
#define mp make_pair
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define lowbit(x) ((x)&(-(x)))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
const int inf=0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> pairs;
///////////////////////read5.1///////////////////////
template<typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {if (ch=='-') flag=true;ch=getchar();}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template<typename T,typename U>
inline void read(T &x,U &y){read(x);read(y);}
template<typename T,typename U,typename V>
inline void read(T &x,U &y,V &z){read(x);read(y);read(z);}
////////////////variables&functions//////////////////
const int maxn=111111;
stack<int> st;
int n,a[maxn],r[maxn],l[maxn];
LL sum[maxn];
int main()
{
    read(n);
    rep(i,1,n) read(a[i]);
    rep(i,1,n) sum[i]=sum[i-1]+a[i];
    a[0]=-1;a[n+1]=-1;
    rep(i,1,n+1)
    {
        if (st.empty()||a[i]>=a[st.top()]) st.push(i);
        else
        {
            while (!st.empty()&&a[i]<a[st.top()]) 
            {
                r[st.top()]=i-1;
                st.pop();
            }
            st.push(i);
        }
    }
    per(i,n,0)
    {
        if (st.empty()||a[i]>=a[st.top()]) st.push(i);
        else
        {
            while(!st.empty()&&a[i]<a[st.top()])
            {
                l[st.top()]=i+1;
                st.pop();
            }
            st.push(i);
        }
    }
    LL ans=-1;
    int ansl,ansr;
    rep(i,1,n) 
    {
        LL temp=(sum[r[i]]-sum[l[i]-1])*a[i];
        if (ans<temp)
        {
            ans=temp;
            ansl=l[i];
            ansr=r[i];
        }
    }
    cout<<ans<<endl<<ansl<<' '<<ansr<<endl;
    return 0;
}