分析

去专门学了笛卡尔树，找了一道模板题来做。由于我们建立的笛卡尔树满足小根堆性质，因此 的子树内的结点的高度都大于等于 。而我们又知道 子树内的下标是一段连续的区间。所以 。通过单调栈构建笛卡尔树，时间复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 110000;
int lc[N],rc[N],st[N],top,n,a[N],si[N];
#define LL long long 
LL ans;
void dfs(int x) {
    if(lc[x]) dfs(lc[x]);
    if(rc[x]) dfs(rc[x]);
    si[x] = si[lc[x]] + si[rc[x]] + 1;
    ans = max(ans,1LL * si[x] * a[x]);
}
int main() {
    while(scanf("%d",&n) && n) {
        for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
        ans = top = 0;memset(lc,0,sizeof(lc));memset(rc,0,sizeof(rc));
        for(int i = 1;i <= n;i++) {
            int k = top;
            while(k && a[i] <= a[st[k]]) k--;
            if(k) rc[st[k]] = i;
            if(k < top) lc[i] = st[k + 1];
            st[++k] = i;top = k;  
        }
        dfs(st[1]);
        printf("%lld\n",ans);
    }
}