【JZOJ7273】数列

by AmanoKumiko

Description

给出数列\(A\)，将其划分，令划分段数为\(m\)

最大化\(\sum_{i=2}^m((B_i-B_{i-1})^2+C)\)

其中\(C\)为给定常数，\(B_i\)为第\(i\)段的最大值

Input

第一行两个整数\(n,C\)

第二行\(n\)个整数，表示\(A\)

Output

一行一个整数表示答案​

Sample Input

5 3
10 1 2 3 5

Sample Output

103

Data Constraint

\(2\le n \le 10^6,1\le A_i \le 10^6,0\le C \le 10^{10}\)

Solution

令\(f_i\)表示最后划分的那段最大值为\(A_i\)时的答案

可以发现一个优美的性质

对某连续三个\(B_i\)，设\(B_{i-1}<B_{i+1}\)（\(B_{i-1}>B_{i+1}\)时同理）

若\(B_i>B_{i+1}\)，则从\(B_{i-1}\)转移一定劣于从\(B_i\)转移

证：

设\(B_{i+1}=B_{i-1}+c=B_{i-1}+a-b\)（后面那种即为先到\(B_i\)，再到\(B_{i+1}\)）

则\(c=a-b\ =>\ c^2=(a-b)^2<a^2+b^2\)

又\(B_{i-1}\)的贡献\(=f_{i-1}+c^2+C\)，\(B_i\)的贡献\(=f_{i-1}+a^2+b^2+2C\)

故证得

那么\(f_i\)就可以从\(f_1\)至\(f_{i-1}\)中任意一个转移（因为不满足上述性质的转移也没有意义，当作可以转移）

写出式子：

\[f_i=max_{j=1}^{i-1}f_j+(A_i-A_j)^2+C=A_i^2+C+max_{j=1}^{i-1}-2A_jAi+f_j+Aj^2 \]

令\(k=-2Aj\)，\(b=fj+Aj^2\)，一颗李超树解决

由于此时直线是无限延伸的，所以李超树插入的复杂度为\(O(N\ log\ N)\)

Code

#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define inf 9223372036854775807
#define LL long long
#define Ld long double
#define N 1000010

int n;
LL a[N],c,f[N],ans;
struct tree{
	int ls[N],rs[N],cnt;
	LL k[N],b[N];
	void ul(int x){if(!ls[x])ls[x]=++cnt;}
	void ur(int x){if(!rs[x])rs[x]=++cnt;}
	void change(int x,LL l,LL r,LL K,LL B){
		if(!k[x]){k[x]=K,b[x]=B;return;}
		LL l1=l*k[x]+b[x],l2=l*K+B,r1=r*k[x]+b[x],r2=r*K+B;
		if(l1>=l2&&r1>=r2)return;
		if(l1<l2&&r1<r2){k[x]=K,b[x]=B;return;}
		Ld cross=1.0*(B-b[x])/(k[x]-K),mid=(l+r)*0.5;
		LL M=l+r>>1;
		if(cross<=mid){
			if(l1>l2){ul(x);change(ls[x],l,M,k[x],b[x]);k[x]=K;b[x]=B;}
			else{ul(x);change(ls[x],l,M,K,B);}
		}else{
			if(l2>l1){ur(x);change(rs[x],M+1,r,k[x],b[x]);k[x]=K;b[x]=B;}
			else{ur(x);change(rs[x],M+1,r,K,B);}
		}
	}
	void query(int x,int l,int r,int pos){
		ans=max(ans,1ll*k[x]*pos+b[x]);
		int mid=l+r>>1;
		if(pos<=mid){if(ls[x])query(ls[x],l,mid,pos);}
		else{if(rs[x])query(rs[x],mid+1,r,pos);}
	}
}t;

LL sqr(LL x){return x*x;}

int main(){
	freopen("array.in","r",stdin);
	freopen("array.out","w",stdout);
	scanf("%d%lld",&n,&c);
	F(i,1,n)scanf("%lld",&a[i]);
	f[1]=0;
	t.cnt=1;
	t.change(1,1,1000000,-a[1]*2ll,sqr(a[1]));
	F(i,2,n){
		ans=-inf;
		t.query(1,1,1000000,a[i]);
		f[i]=ans+c+sqr(a[i]);
		t.change(1,1,1000000,-a[i]*2ll,f[i]+sqr(a[i]));
	}
	printf("%lld",f[n]);
	return 0;
}