loj#2483. 「CEOI2017」Building Bridges 斜率优化 cdq分治

loj#2483. 「CEOI2017」Building Bridges

链接

https://loj.ac/problem/2483

思路

\[f[i]=f[j]+(h[i]-h[j])^2+(sum[i-1]-sum[j])\]
\[f[i]=f[j]+h[i]^2+h[j]^2-2*h[i]*h[j]+sum[i-1]-sum[j]\]
\[sum[j]-f[j]-h[j]^2=(-2*h[j])*h[i]+sum[i-1]+h[i]^2-f[i]\]
\[f[j]+h[j]^2-sum[j]=2*h[j]*h[i]-sum[i-1]-h[i]^2+f[i]\]
\[x=h[j],y=f[j]+h[j]^2-sum[j]\]
\[k=2*h[i],b=没用\]
然后cdq维护一下凸包

细节

首先按照k排序(k是已知的)，保证询问不再二分凸包(\(log^2n\))而是使用单调队列(\(logn\))。
计算斜率的函数一定要写好了。
还有最后按照x排序的函数也要一起写好。
会受影响的

大体流程

if(l==r) return;
按照mid把p分成两半
cdq(l,mid)
建立左边的凸包
左边的凸包更新右边的答案
cdq(mid+1,r)
按照x排序p
ps:p就是个结构体存很多东西

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=2e5+7;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll read() {
    ll x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
ll n,h[N],sum[N],f[N];
struct node {
    ll k,x,y,id;
    bool operator < (const node &b) const {
        return k<b.k;
    }
}q[N],t[N];
ll stak[N],top;
double get_k(ll a,ll b) {
    if(!b) return inf;
    if(q[a].x==q[b].x) return q[a].y<=q[b].y?inf:-inf;
    return 1.0*(q[a].y-q[b].y)/(q[a].x-q[b].x);
}
void solve(ll l,ll r) {
    if(l==r) {
        q[l].y=f[l]+h[l]*h[l]-sum[l];
        return;
    }
    ll mid=(l+r)>>1,l1=l,l2=mid+1;

    //sort q according to id
    for(ll i=l;i<=r;++i) {
        if(q[i].id<=mid) t[l1++]=q[i];
        else t[l2++]=q[i];
    }
    for(ll i=l;i<=r;++i) q[i]=t[i];
    
    solve(l,mid);

    //build a convex hull on the left
    top=0;
    for(ll i=l;i<=mid;++i) {
        while(top>1&&get_k(stak[top-1],stak[top])>get_k(stak[top-1],i)) top--;
        stak[++top]=i;
    }
    stak[++top]=0;

    //update ans on the right
    for(ll dsr=mid+1,DSR=1;dsr<=r;++dsr) {
        while(DSR<top&&get_k(stak[DSR],stak[DSR+1])<q[dsr].k)
            DSR++;
        ll i=q[dsr].id,j=q[stak[DSR]].id;
        f[i]=min(f[i],f[j]+(h[i]-h[j])*(h[i]-h[j])+sum[i-1]-sum[j]);
    }
    solve(mid+1,r);

    //sort q according to x
    l1=l,l2=mid+1;
    for(ll i=l;i<=r;++i) {
        if(((q[l1].x<q[l2].x||(q[l1].x==q[l2].x&&q[l1].y<q[l2].y)||l2>r))&&l1<=mid) t[i]=q[l1++];
        // if(((p[l1].x<p[l2].x||(fabs(p[l1].x-p[l2].x)<eps&&p[l1].y<p[l2].y)||l2>r))&&l1<=mid)
        else t[i]=q[l2++];
    }
    for(ll i=l;i<=r;++i) q[i]=t[i];
}
int main() {
    n=read();
    for(ll i=1;i<=n;++i) h[i]=read();
    for(ll i=1;i<=n;++i) sum[i]=sum[i-1]+read();
    for(ll i=1;i<=n;++i) q[i].x=h[i],q[i].k=2*h[i],q[i].id=i;
    memset(f,0x3f,sizeof(f));f[1]=0;
    sort(q+1,q+1+n);
    solve(1,n);
    printf("%lld\n",f[n]);
    return 0;
}