题解：P11585 [KTSC 2022 R1] 直方图

云浅知处 · 2025-04-10 15:24:13 · 题解

f(1)

建笛卡尔树，那么答案一定是选笛卡尔树上的一个矩形。容易做到 O(n)。

f(2)

如果两个矩形横坐标区间不交，只需要枚举分界点 i，计算在直线 x=i 前后的最大矩形面积，相加即可。

对于相交的情况，两个一定在笛卡尔树上成祖孙关系，考虑如果选了 u,v 这两个点，其中 u 是 v 的祖先，其贡献为 -len_v\times h_u+len_u\times h_u+len_v\times h_v。

在祖先处统计，李超树合并维护 (-len,len\times h) 的这些直线即可。

f(3)

对于三个矩形的横坐标区间互不相交的情况，DP 即可。

如果前两个矩形的横坐标区间都和第三个不交，类似 k=2 的两个不交的部分做一遍即可。

设选的三个矩形对应到笛卡尔树上的节点分别为 u,v,w。

如果 u,v,w 依次为祖孙关系就只需要把 k=2 的再做一遍。

具体来说我们设 G_v 表示选一个 v 和 v 的子孙 w，其 -len_w\times h_v+len_v\times h_v+len_w\times h_w 的最大值，再设 H_u 表示选一个 u 和 u 的子孙 v，其 -len_v\times h_u+len_u\times h_u+G_v 的最大值，两个都可以用李超树优化。

剩下的唯一情况是选一个祖先 u，然后选两个 v,w 满足 v,w 互不为祖孙关系，造成的贡献为

我们考虑放宽限制，发现当 u 不为 v,w 的祖先时，这个东西不会算的更大。考虑对 u 不做任何限制，只钦定 v,w 不交。那么如果没有不交的限制，我们需要对一个 (-len_i,len_i\times h_i) 这样的东西求一下凸包，然后和自己做闵可夫斯基和。

考虑如何处理不交的限制。对序列建线段树，每个子树变成一个区间 [l,r]，考虑两个不交区间 [l_1,r_1],[l_2,r_2]，不妨设 r_1<l_2，我们在 \text{LCA}(r_1,l_2) 处统计这个贡献。

具体来说，我们对每个线段树节点维护两个凸包 L,R，然后对每个区间 [l,r]，我们在 l 的所有祖先的 L 凸包里面插入这个点，r 的所有祖先的 R 凸包里面插入这个点，然后我们对每个线段树节点，把他左儿子的 R 凸包和右儿子的 L 凸包做闵可夫斯基和，把得到的这些点放到总的点集里面，最后再对总的点集求一遍凸包。求出这个凸包之后，再枚举 u 计算即可。

实现的时候写成分治的形式可以减小一部分常数。综上，总复杂度 O(n\log n)。

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}

template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}

const int N=5e5+5;
int n,a[N],pl[N],pr[N],fa[N],len[N],H;
ll pre[N],suf[N];
int rt=0;
vector<int>G[N];

ll ans1,ans2,ans3;

void build(){
    vector<int>stk(n+1);int top=0;
    for(int i=1;i<=n;i++){
        while(top>0&&a[stk[top]]>a[i])top--;
        pl[i]=stk[top]+1,stk[++top]=i;
    }
    top=0,stk[0]=n+1;
    for(int i=n;i>=1;i--){
        while(top>0&&a[stk[top]]>=a[i])top--;
        pr[i]=stk[top]-1,stk[++top]=i;
    }

    for(int i=1;i<=n;i++){
        len[i]=pr[i]-pl[i]+1;
        if(pl[i]==1&&pr[i]==n)rt=i;
        else if(pl[i]==1)fa[i]=pr[i]+1;
        else if(pr[i]==n)fa[i]=pl[i]-1;
        else fa[i]=(a[pl[i]-1]>a[pr[i]+1]?pl[i]-1:pr[i]+1);

        if(i!=rt)G[fa[i]].emplace_back(i);
    }

    for(int i=1;i<=n;i++){
        ll cur=1ll*(pr[i]-pl[i]+1)*a[i];
        cmax(suf[pl[i]],cur),cmax(pre[pr[i]],cur),cmax(ans1,cur);
    }
    for(int i=1;i<=n;i++)cmax(pre[i],pre[i-1]);
    for(int i=n;i>=1;i--)cmax(suf[i],suf[i+1]);
}

struct LINE{
    ll k,b;
    ll val(int x){return k*x+b;}
    LINE(ll K=0,ll B=0):k(K),b(B){}
};
bool cmp(LINE A,LINE B,int pos){
    return A.val(pos)>B.val(pos);
}

const ll INF=1e12;

int root[N];
const int M=N*32;
struct LiChao{
    LINE d[M];int tot,ls[M],rs[M];
    #define ls(p) (ls[p])
    #define rs(p) (rs[p])
    void reset(){
        memset(ls,0,sizeof(ls)),memset(rs,0,sizeof(rs)),tot=0;
        for(int i=0;i<M;i++)d[i]=LINE(-INF,-INF);
    }
    void clear(){
        for(int i=1;i<=tot;i++)d[i]=LINE(-INF,-INF),ls[i]=rs[i]=0;
        tot=0;
    }
    void upd(int ql,int qr,int &p,LINE A){
        if(!p)return d[p=++tot]=A,void();
        int mid=(ql+qr)>>1;
        if(cmp(A,d[p],mid))swap(d[p],A);
        if(cmp(A,d[p],ql))upd(ql,mid,ls(p),A);
        if(cmp(A,d[p],qr))upd(mid+1,qr,rs(p),A);
    }
    ll qval(int x,int ql,int qr,int p){
        if(!p)return -INF;
        int mid=(ql+qr)>>1;ll ans=d[p].val(x);
        if(x<=mid)cmax(ans,qval(x,ql,mid,ls(p)));
        if(x>mid)cmax(ans,qval(x,mid+1,qr,rs(p)));
        return ans;
    }
    int merge(int p,int q,int l,int r){
        if(!p||!q)return p^q;
        upd(l,r,p,d[q]);int mid=(l+r)>>1;
        if(l!=r)ls[p]=merge(ls[p],ls[q],l,mid),rs[p]=merge(rs[p],rs[q],mid+1,r);
        return p;
    }
    #undef ls
    #undef rs
}T;

ll val[N];
void solve2(){
    function<void(int)>dfs=[&](int u){
        for(int v:G[u])dfs(v),root[u]=T.merge(root[u],root[v],1,H);
        T.upd(1,H,root[u],LINE(-len[u],1ll*len[u]*a[u]));
        val[u]=T.qval(a[u],1,H,root[u])+1ll*len[u]*a[u];
    };

    T.reset(),dfs(rt);
    for(int i=1;i<=n+1;i++)cmax(ans2,pre[i-1]+suf[i]);
    for(int i=1;i<=n;i++)cmax(ans2,val[i]);
}

struct P{ll x,y;P(ll _x=0,ll _y=0):x(_x),y(_y){}};
P operator-(P A,P B){return P(A.x-B.x,A.y-B.y);}
P operator+(P A,P B){return P(A.x+B.x,A.y+B.y);}
bool operator<(P A,P B){
    if(A.x!=B.x)return A.x<B.x;
    return A.y<B.y;
}
ll Cross(P A,P B){return A.x*B.y-A.y*B.x;}
bool chk(int k,P A,P B){// slope(A,B) > k ?
    return (B.y-A.y)>1ll*(B.x-A.x)*k;
}
struct kevin{
    vector<P>stk;int p=0;
    void clr(){stk.clear();p=0;}
    void ins(P A){
        while(stk.size()>=2&&Cross(stk.back()-A,stk[stk.size()-2]-A)<=0)stk.pop_back();
        stk.emplace_back(A);
    }
    ll qry(int k){
        if(stk.empty())return -INF;
        while(p+1<stk.size()&&chk(k,stk[p],stk[p+1]))p++;
        return -1ll*stk[p].x*k+stk[p].y;
    }
};

kevin All;
ll all_ps[N<<2];
void work(vector<P>A,vector<P>B){
    if(A.empty()||B.empty())return ;

    vector<P>C;
    for(int i=A.size()-1;i>=1;i--)A[i]=A[i]-A[i-1];
    for(int i=B.size()-1;i>=1;i--)B[i]=B[i]-B[i-1];
    int it=1;
    C.emplace_back(A[0]+B[0]);
    for(int i=1;i<A.size();i++){
        while(it<B.size()&&Cross(B[it],A[i])<0)C.emplace_back(B[it++]);
        C.emplace_back(A[i]);
    }
    while(it<B.size())C.emplace_back(B[it++]);
    for(int i=1;i<C.size();i++)C[i]=C[i]+C[i-1];

    for(auto W:C)cmax(all_ps[W.x],W.y);
}

vector<P>bl[N],br[N];
pair<vector<P>,vector<P> > Solve(int l,int r){
    if(l==r)return mk(bl[l],br[l]);
    int mid=(l+r)>>1;
    auto Lp=Solve(l,mid),Rp=Solve(mid+1,r);
    vector<P>curL,curR;
    auto wL=Lp.fi,wR=Rp.fi;
    int itp=0;
    for(int i=0;i<wL.size();i++){
        while(itp<wR.size()&&wR[itp]<wL[i])curL.emplace_back(wR[itp++]);
        curL.emplace_back(wL[i]);
    }
    while(itp<wR.size())curL.emplace_back(wR[itp++]);

    wL=Lp.se,wR=Rp.se,itp=0;
    for(int i=0;i<wL.size();i++){
        while(itp<wR.size()&&wR[itp]<wL[i])curR.emplace_back(wR[itp++]);
        curR.emplace_back(wL[i]);
    }
    while(itp<wR.size())curR.emplace_back(wR[itp++]);

    kevin L,R;L.clr(),R.clr();
    for(auto W:Lp.se)L.ins(W);
    for(auto W:Rp.fi)R.ins(W);
    work(L.stk,R.stk);

    return mk(curL,curR);
}

void solve3(){
    for(int i=1;i<=n;i++)cmax(ans3,val[i]+max(pre[pl[i]-1],suf[pr[i]+1]));

    vector<vector<ll> >dp(n+1,vector<ll>(4));
    vector<vector<pair<ll,int> > >Is(n+1);
    for(int i=1;i<=n;i++)Is[pr[i]].emplace_back(mk(1ll*len[i]*a[i],pl[i]-1));
    for(int i=1;i<=n;i++){
        for(int c=1;c<=3;c++){
            cmax(dp[i][c],dp[i-1][c]);
            for(auto [val,j]:Is[i])cmax(dp[i][c],dp[j][c-1]+val);
        }
        cmax(ans3,dp[i][3]);
    }

    function<void(int)>dfs=[&](int u){
        for(int v:G[u])dfs(v),root[u]=T.merge(root[u],root[v],1,H);
        cmax(ans3,T.qval(a[u],1,H,root[u])+1ll*len[u]*a[u]);
        T.upd(1,H,root[u],LINE(-len[u],val[u]));
    };
    for(int i=1;i<=n;i++)root[i]=0;
    T.reset(),dfs(rt);

    vector<int>ids(n);
    for(int i=0;i<n;i++)ids[i]=i+1;

    for(int i=1;i<=n;i++)br[pr[i]].emplace_back(P(len[i],1ll*len[i]*a[i])),bl[pl[i]].emplace_back(P(len[i],1ll*len[i]*a[i]));
    for(int i=1;i<=n;i++)sort(br[i].begin(),br[i].end()),sort(bl[i].begin(),bl[i].end());
    for(int i=1;i<=n;i++)all_ps[i]=-INF;
    Solve(1,n);
    for(int i=1;i<=n;i++)if(all_ps[i]>-INF){
        auto W=P(i,all_ps[i]);
        All.ins(W);
    }

    sort(ids.begin(),ids.end(),[&](int x,int y){return a[x]>a[y];});
    for(int i:ids)cmax(ans3,All.qry(a[i])+1ll*len[i]*a[i]);
}

vector<ll>max_area(vector<int>hh){
    n=hh.size();
    for(int i=1;i<=n;i++)a[i]=hh[i-1];
    for(int i=1;i<=n;i++)cmax(H,a[i]);

    build(),solve2(),solve3();

    vector<ll>ret;
    ret.emplace_back(ans1),ret.emplace_back(ans2),ret.emplace_back(ans3);
    return ret;
}

signed main(void){

    n=read();
    for(int i=1;i<=n;i++)a[i]=read(),cmax(H,a[i]);

    build(),solve2(),solve3();
    cout<<ans1<<" "<<ans2<<" "<<ans3<<endl;

    return 0;
}