题解：CF1638F Two Posters

· · 题解

讨论矩形的横坐标区间关系，分为不交、包含和交错。

其中不交直接暴力即可。

考虑包含的情况，容易发现其等价于在第 i 个位置高 h_i 的直方图上选两个叠在一起的矩形，使得面积和最大。

容易通过调整法发现此时下方的矩形的上边界应该尽可能靠上。因此下方矩形只有 O(n) 种不同的情况，枚举下方矩形，再 O(n) 求解上方最大矩形，复杂度 O(n^2)。

考虑交错的情况，考虑枚举两个矩形横坐标的并 [L,R] 和横坐标的交 [l,r]，设矩形高度分别为 A,B，写出 h 对 A,B 的约束条件：

\min_{i\in [L,l)} h_i\geq A,\qquad \min_{i\in [l,r]} h_i\geq A+B,\qquad \min_{i\in (r,R]} h_i\geq B.

由此可以得出 O(n^4) 做法。

记 Lmin=\min_{i\in [L,l)} h_i,\ Rmin=\min_{i\in (r,R]} h_i,\ Mmin=\min_{i\in [l,r]} h_i。

约束条件：Lmin \geq A,\ Mmin \geq A+B,\ Rmin \geq B.

不难发现最优解必定卡满不等式的至少两个上界，假设确定了 L,l,r,R,A,B，答案为 A(r-L+1)+B(R-l+1)，若只卡满了一个上界，可以调整出其他不劣的解。

由于卡到 A,A+B 和 A+B,B 是对称的，所以本质需要分讨两种情况。

第一种情况：卡到 A,B 的上界。

此时对于一个 [L,R]，其答案为 (r-L+1)Lmin+(R-l+1)Rmin，条件是 Lmin+Rmin\leq Mmin。

预处理每个 L 的 Lmin 和每个 R 的 Rmin，对一个固定的 L 以及 Lmin，合法的 R 必为一段后缀，因此预处理 suf_i=\max_{R\geq i} (R-l+1)Rmin_{R}，双指针即可。

对固定的 l,r 可以 O(n) 求解，总共 O(n^3)。

第二种情况：卡到 A 和 A+B 的上界。

此时对于一个 [L,R]，其答案为 (r-L+1)Lmin+(R-l+1)(Mmin-Lmin)，条件是 Rmin\geq Mmin-Lmin。

预处理每个 L 的 Lmin 和每个 R 的 Rmin，对一个固定的 L 以及 Lmin，R 必定取到 Rmin\geq Mmin-Lmin 的最大 R，因此双指针即可，这部分同样可以做到 O(n^3)。

考虑优化枚举 l,r 部分，容易发现在 h_{l-1}\geq Mmin 时令 l\gets l-1 一定不劣。h_{r+1}\geq Mmin 同理。

因此只需要枚举 h_{l-1},g_{r+1}<Mmin 的情况，即只需要枚举 O(n) 个 [l,r]，复杂度 O(n^2)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll h[10005],ans;
int lst[10005],nxt[10005];
int st[10005],tp;
void init(){
    for(int i=1;i<=n;i++){
        while(tp&&h[st[tp]]>h[i]){
            nxt[st[tp]]=i-1;
            st[tp--]=0;
        }
        st[++tp]=i;
    }
    while(tp) nxt[st[tp]]=n,st[tp--]=0;
    for(int i=n;i>=1;i--){
        while(tp&&h[st[tp]]>h[i]){
            lst[st[tp]]=i+1;
            st[tp--]=0;
        }
        st[++tp]=i;
    }
    while(tp) lst[st[tp]]=1,st[tp--]=0;
}
ll calc(int l,int r,ll k=0){//计算h[l,r]-k的最大矩形面积 
    if(l>r) return 0;
    ll res=0;
    for(int i=l;i<=r;i++){
        res=max(res,1ll*(min(r,nxt[i])-max(l,lst[i])+1)*(h[i]-k));
    }
    return res;
}
ll tmpA[10005],tmpB[10005],suf[10005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    init(); 
    for(int i=1;i<=n;i++) ans=max(ans,calc(1,i)+calc(i+1,n));
    for(int i=1;i<=n;i++) ans=max(ans,calc(lst[i],nxt[i],h[i])+h[i]*(nxt[i]-lst[i]+1));
    for(int i=1;i<=n;i++){
        ll mn=h[i];
        int L=lst[i],R=nxt[i];
        if(L==1||R==n) continue;
        //A+B<=mn
        ll A=mn;
        for(int l=L-1;l>=1;l--){
            A=min(A,h[l]);
            tmpA[l]=A;
        }
        ll B=mn;
        for(int r=R+1;r<=n;r++){
            B=min(B,h[r]);
            tmpB[r]=B; 
        }
        for(int r=n;r>=1;r--){
            suf[r]=max(suf[r+1],(r-L+1)*tmpB[r]);
        }
        int r=R+1;
        for(int l=1;l<=L-1;l++){//A,B
            while(r<=n&&tmpA[l]+tmpB[r]>mn) r++;
            if(r>n) break;
            ans=max(ans,1ll*(R-l+1)*tmpA[l]+suf[r]);
        }
        r=R;
        for(int l=1;l<=L-1;l++){//A,A+B
            while(r+1<=n&&mn-tmpA[l]<=tmpB[r+1]) r++;
            if(r>R) ans=max(ans,1ll*(R-l+1)*tmpA[l]+1ll*(r-L+1)*(mn-tmpA[l]));
        }
        int l=L;
        for(int r=n;r>=R+1;r--){//A+B,B
            while(l-1>=1&&mn-tmpB[r]<=tmpA[l-1]) l--;
            if(l<L) ans=max(ans,1ll*(R-l+1)*(mn-tmpB[r])+1ll*(r-L+1)*tmpB[r]);
        }
    }
    cout<<ans<<"\n";
    return 0;
}