P7926
spider_oyster
·
·
题解
好像没人用李超线段树？我来写一发。
记 a 的前缀和数组为 s，可以得出状态转移方程：
设 $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\}$。
由于懒，前面的那一坨我还是选择用李超维护。
但这题数据太强了，细节有点多。我初始化写挂了，调了半天。
```cpp
#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';
}
}
```