建造桥梁 也是cdq解决斜率优化的板子
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,f[100005],q[100005],back,front,qzh[100005];
struct node{
int h,w,id;
}a[100005];
bool cmp(node x,node y){
return x.h<y.h;
}
bool cmp1(node x,node y){
return x.id<y.id;
}
int y(int i){
return f[a[i].id]+a[i].h*a[i].h-qzh[a[i].id];
}
int x(int i){
return a[i].h;
}
void cdq(int l,int r){
if(l==r)return;
int mid=(l+r)/2;
cdq(l,mid);
sort(a+l,a+mid+1,cmp);
sort(a+mid+1,a+r+1,cmp);
front=0,back=1;
for(int i=l;i<=mid;i++){
int tp=0;
while(front>back){
if(x(i)-x(q[front])==0){
if(y(i)<y(q[front]))front--;
else {
tp=1;
break;
}
}
else if((y(q[front])-y(q[front-1]))*(x(i)-x(q[front]))>=/*就是这个 换成>就会wa一个点*/(y(i)-y(q[front]))*(x(q[front])-x(q[front-1])))front--;
else break;
}
if(tp)continue;
q[++front]=i;
}
for(int i=mid+1;i<=r;i++){
while(front>back&&y(q[back])-2*x(q[back])*a[i].h>y(q[back+1])-2*x(q[back+1])*a[i].h)back++;
f[a[i].id]=min(f[a[i].id],y(q[back])-2*x(q[back])*a[i].h+a[i].h*a[i].h+qzh[a[i].id-1]);
}
sort(a+l,a+r+1,cmp1);
cdq(mid+1,r);
}
main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
f[i]=1e18;
scanf("%lld",&a[i].h);
a[i].id=i;
}
f[1]=0;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i].w);
qzh[i]=qzh[i-1]+a[i].w;
}
cdq(1,n);
for(int i=1;i<=n;i++)printf("%lld\n",f[i]);
printf("%lld",f[n]);
}