P4655 [CEOI2017] Building Bridges

斜率优化 + CDQ 分治，或者使用李超线段树。

解法一：斜率优化 + CDQ 分治

设 $s_i=\sum_{j=1}^i w_i$，容易得到状态转移方程：

$$f(i)=\min_j f(j)+(h_i-h_j)^2+s_{i-1}-s_j$$

平方和很斜率优化，化成斜率优化的形式：

$$f(j)+h_j^2-s_j=2h_ih_j+f(i)-h_i^2-s_{i-1}$$

得到 $y=kx+b$ 的形式，视 $f(j)+h_j^2-s_j$ 为 $y$， $2h_i$ 为 $k$， $h_j$ 为 $x$，$f(i)-h_i^2-s_{i-1}$ 为 $b$。但是 $k,x$ 都不单调，我们不能通过普通的单调队列来维护凸包。当然可以使用平衡树动态维护凸包，不过我们也考虑 CDQ 分治：先处理左边区间的答案，处理完之后按照 $h_i$ 排序，再考虑对右边区间的贡献即可。最终时间复杂度为 $\mathcal O(n\log n)$。

解法二：李超线段树

把平方和拆开再根据下标分下类：

$$f(i)-h_i^2-s_{i-1}=\min_j -2h_ih_j+f(j)+h_j^2-s_j$$

那么我们只需要在李超线段树上查询，再插入 $k=-2h_i,b=f(i)-h_i^2-s_i$ 的线段 $y=kx+b$。因为是全局插入所以不需要拆分线段，所以时间复杂度为 $\mathcal O(n\log V )$。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
using ll=long long;
const int N=5e5+10,M=1e6+10;
const ll INF=1e18;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void ckmin(T &x,T y){x=x<y?x:y;};
int n;
int h[N];
ll sum[N],f[N];

struct Seg
{
    struct Line{ll k,b;ll f(ll x){return k*x+b;}}a[N];
    struct Node
    {
        int l,r;
        int s;
    }tr[M<<2];
    ll f(int i,ll pos){return a[i].f(pos);}
    void add(int i,ll k,ll b)
    {
        a[i].k=k,a[i].b=b;
        modify(1,i);
    }
    void build(int x,int l,int r)
    {
        tr[x].l=l,tr[x].r=r,tr[x].s=0;
        if(l==r)return ;
        int mid=l+r>>1;
        build(x<<1,l,mid),build(x<<1|1,mid+1,r);
    }
    void modify(int x,int p)
    {
        if(tr[x].l==tr[x].r)
            if(f(p,tr[x].l)<f(tr[x].s,tr[x].l))
                return tr[x].s=p,void();
        int mid=tr[x].l+tr[x].r>>1;
        if(f(p,mid)<f(tr[x].s,mid))swap(p,tr[x].s);
        if(f(p,tr[x].l)<f(tr[x].s,tr[x].l))return modify(x<<1,p);
        if(f(p,tr[x].r)<f(tr[x].s,tr[x].r))return modify(x<<1|1,p);
    }
    ll query(int x,int pos)
    {
        ll res=f(tr[x].s,pos);
        if(tr[x].l==tr[x].r)return res;
        int mid=tr[x].l+tr[x].r>>1;
        if(pos<=mid)ckmin(res,query(x<<1,pos));
        else ckmin(res,query(x<<1|1,pos));
        return res;
    }
}t;
inline ll K(int i){return -2*h[i];}
inline ll B(int i){return f[i]+1ll*h[i]*h[i]-sum[i];}

int main()
{
    read(n);
    for(int i=1;i<=n;i++)read(h[i]);
    for(int i=1;i<=n;i++)read(sum[i]),sum[i]+=sum[i-1];
    memset(f,0x3f,sizeof(f));
    f[1]=0;
    t.build(1,0,M-10);
    t.a[0].b=INF;
    for(int i=2;i<=n;i++)
    {
        t.add(i-1,K(i-1),B(i-1));
        f[i]=t.query(1,h[i])+1ll*h[i]*h[i]+sum[i-1];
    }
    printf("%lld\n",f[n]);
    return 0;
}