自动搬运

查看原文

来自洛谷，原作者为

	spider_oyster 蜘蛛到死丝方尽，生蚝成壳液始干

搬运于2025-08-24 22:34:22，当前版本为作者最后更新于2023-05-21 19:31:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

好像没人用李超线段树？我来写一发。

记 $a$ 的前缀和数组为 $s$，可以得出状态转移方程：

$f_i=\min\limits_{j=0}^{i-1}f_j+(s_i-s_j-L)^2$。

设 $g_i=s_i-L$，化简式子如下：

$f_i=\min\limits_{j=0}^{i-1}f_j+g_i^2+s_j^2-2\times s_j\times g_i$。

$f_i=\min\limits_{j=0}^{i-1}(-2\times s_j\times g_i+s_j^2)+g_i^2$。

于是直接李超线段树维护上述式子最小值次小值。

记上述式子的次小值为 $se$，第二小不和谐度为 $f'$，则

$f'_ i=\min\{ \min\limits_{j=0}^{i-1}f'_ j+g_i^2+s_j^2-2\times s_j\times g_i,se\}$。

由于懒，前面的那一坨我还是选择用李超维护。

但这题数据太强了，细节有点多。我初始化写挂了，调了半天。

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mi first
#define se second
#define mid ((l+r)>>1)
using namespace std;

const int N=2e5+5;
int n,L,id2[N<<2];
ll s[N],f[N],f2[N];
pii id[N<<2];
inline ll g(int i) {return s[i]-L;}

struct line{
    ll k,b;
    ll operator()(const int &i) {return k*g(i)+b;}
}p[N],p2[N];

//只能有一条编号 0 的直线，我就是这里挂了
void init() {for(int i=1;i<=n*4;i++) id[i]={n+1,n+1};id[1]={0,n+1};}

void upd(int u,int k=1,int l=1,int r=n)
{
    pii &v=id[k];
    if(p[u](mid)<p[v.mi](mid)) swap(v.mi,v.se),swap(v.mi,u);
    else if(p[u](mid)<p[v.se](mid)) swap(v.se,u);
    if(p[u](l)<max(p[v.mi](l),p[v.se](l))) upd(u,k<<1,l,mid);
    if(p[u](r)<max(p[v.mi](r),p[v.se](r))) upd(u,k<<1|1,mid+1,r);
}
pii query(int x,int k=1,int l=1,int r=n)
{
    pii u=id[k],v;
    if(l==r) return u;
    v=(x<=mid?query(x,k<<1,l,mid):query(x,k<<1|1,mid+1,r));
    int a[4]={u.mi,u.se,v.mi,v.se};
    //懒，直接排序了
    sort(a,a+4,[x](int &a,int &b){return p[a](x)<p[b](x);});
    return {a[0],a[1]};
}

void upd2(int u,int k=1,int l=1,int r=n)
{
    int &v=id2[k];
    if(p2[u](mid)<p2[v](mid)) swap(u,v);
    if(p2[u](l)<p2[v](l)) upd2(u,k<<1,l,mid);
    if(p2[u](r)<p2[v](r)) upd2(u,k<<1|1,mid+1,r);
}
int query2(int x,int k=1,int l=1,int r=n)
{
    int u=id2[k],v;
    if(l==r) return u;
    v=(x<=mid?query2(x,k<<1,l,mid):query2(x,k<<1|1,mid+1,r));
    return p2[u](x)<p2[v](x)?u:v;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>L;
    for(int i=1;i<=n;i++) cin>>s[i],s[i]+=s[i-1];
    init();
    p[n+1].b=f2[0]=f2[1]=1e16;//把直线 n+1 的值设为 inf
    for(int i=1;i<=n;i++)
    {
        auto [j1,j2]=query(i);
        int j3=query2(i);
        f[i]=f[j1]+(g(i)-s[j1])*(g(i)-s[j1]);
        ll x=f[j2]+(g(i)-s[j2])*(g(i)-s[j2]);
        ll y=f2[j3]+(g(i)-s[j3])*(g(i)-s[j3]);
        p[i]={-2*s[i],f[i]+s[i]*s[i]};
        upd(i);
        cout<<f[i];
        if(i!=1)
        {
            f2[i]=min(x,y);
            p2[i]={-2*s[i],f2[i]+s[i]*s[i]};
            upd2(i);
            cout<<' '<<f2[i];
        }
        cout<<'\n';
    }
}