题解：P15884 [ICPC 2026 NAC] Jelly Fusion

Aux_sky · 2026-10-20 16:12:16 · 题解

先考虑链怎么做。

我们相当于要划分成若干个区间，每个区间的权值 v_{l,r} 为 [l,r] 的 h_{\max}\times w_{\max}，直接转移可以做到 \mathcal O(n^2)。

考虑对于一个左端点，如果其既不是 h_{\max} 也不是 w_{\max}，我们显然是可以把左端点右移并新开一段，使答案更优，右端点同理。

所以说左右端点一个是 h_{\max} 一个是 w_{\max}。

转移变为 \displaystyle f_{i}=\max_{j\le i}\{f_{j-1}+h_jw_i,f_{j-1}+w_jh_i\}，这是一个 \max kx+b 的形式，直接用李超树做就可以做到 \mathcal O(n\log V)。

对于原题，全局 h_{\max} 的位置要么是一段的开头要么是一段的结尾，从这里断开做两遍链的问题即可。

::::success[Code]

int n,st;
ll h[N],w[N],mx,ans,f[N],a[N],b[N];
struct node{ll k,b;};
ll val(node s,ll x){return s.k*x+s.b;}
struct Segtree{
    node tr[M<<2];
    void init(){for(int i=0;i<(M<<2);++i)tr[i]={-1,-1};}
    void modify(int l,int r,int x,node s){
        if(tr[x].k==-1){tr[x]=s;return;}
        if(l==r){
            if(val(tr[x],l)<val(s,l))tr[x]=s;
            return;
        }
        int mid((l+r)>>1);
        if(val(tr[x],mid)<val(s,mid))swap(tr[x],s);
        if(val(s,l)>val(tr[x],l))modify(l,mid,x<<1,s);
        else modify(mid+1,r,x<<1|1,s);
    }
    ll query(int l,int r,int x,int p){
        if(l==r)return val(tr[x],p);
        int mid((l+r)>>1);
        if(mid>=p)return max(query(l,mid,x<<1,p),val(tr[x],p));
        return max(query(mid+1,r,x<<1|1,p),val(tr[x],p));
    }
}T,G;
ll Find(){
    T.init(),G.init();
    for(int i=1;i<=n;++i){
        T.modify(1,1e6,1,{a[i],f[i-1]});
        G.modify(1,1e6,1,{b[i],f[i-1]});
        f[i]=max(T.query(1,1e6,1,b[i]),G.query(1,1e6,1,a[i]));
    }
    return f[n];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld%lld",&h[i],&w[i]);
        if(mx<h[i])mx=h[i],st=i;
    }
    int m(0);
    for(int i=st;i<=n;++i)a[++m]=h[i],b[m]=w[i];
    for(int i=1;i<st;++i)a[++m]=h[i],b[m]=w[i];
    ans=Find(),m=0;
    for(int i=st+1;i<=n;++i)a[++m]=h[i],b[m]=w[i];
    for(int i=1;i<=st;++i)a[++m]=h[i],b[m]=w[i];
    ans=max(ans,Find());
    printf("%lld",ans);
    return 0;
}

::::