题意：
给出N个柱子，现在要顺次连接它们（从1连到N），每次连接的代价为高度之差的平方。
如果某些柱子不连，那么需要用Wi的代价销毁它。
求最小代价。
神奇的链接（一个叫陈万洲的抄袭狗的博客） ↓
https://www.yunyii.cn/article/Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDU0MDY5L2FydGljbGUvZGV0YWlscy84MzM4MTk5Mg==
分析：
很显然的DP
很显然的斜率优化
推出来一坨东西后，发现需要满足的斜率(2×hi)(2\times h_i)(2×hi?)不是单调的。
所以。。。CDQ分治啊。。。
先按hih_ihi?升序排列。
在处理[l,r][l,r][l,r]区间时，先按照编号，分为较小的较大的两部分。（因为只有编号较小的会对编号较大的做出贡献）
然后先处理小的部分，把小的部分的DP值算出来。
然后再通过小的部分来更新大的部分的答案。
然后再处理右半部分。
当然，返回的时候不能忘了把顺序还原为按h值升序
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
typedef long long ll;
struct node{
ll x,y,id;
}p[MAXN],tmp[MAXN];
int q[MAXN];
ll dp[MAXN],h[MAXN],w[MAXN],pre[MAXN];
int n;
bool sort_by_x(const node &a,const node &b){
if(a.x!=b.x)return a.x<b.x;return a.id<b.id;
}
void CDQ(int l,int r){
// PF("{%d %d}\n",l,r);
// for(int i=1;i<=n;i++)
// PF("[%lld %lld %lld %lld]\n",p[i].x,p[i].id,p[i].y,dp[p[i].id]);
// PF("-------------------\n");if(l==r){
p[l].y=dp[l]+h[l]*h[l]-pre[l]; return ;}int mid=(l+r)>>1;int xl=l,xr=mid+1;for(int i=l;i<=r;i++){
if(p[i].id<=mid)tmp[xl++]=p[i];elsetmp[xr++]=p[i];}for(int i=l;i<=r;i++)p[i]=tmp[i];CDQ(l,mid);int head=1,tail=0;for(int i=l;i<=mid;i++){
while(head<tail&&1.0*(p[i].y-p[q[tail]].y)*(1.0*(p[q[tail]].x-p[q[tail-1]].x))<=1.0*(p[q[tail]].y-p[q[tail-1]].y)*(1.0*(p[i].x-p[q[tail]].x)))tail--;q[++tail]=i;}for(int id=mid+1;id<=r;id++){
int i=p[id].id;while(head<tail&&1.0*(p[q[head+1]].y-p[q[head]].y)<=2.0*h[i]*(1.0*(p[q[head+1]].x-p[q[head]].x)))head++;int j=p[q[head]].id;dp[i]=min(dp[i],dp[j]+(h[i]-h[j])*(h[i]-h[j])+pre[i-1]-pre[j]);}CDQ(mid+1,r);xl=l,xr=mid+1;for(int i=l;i<=r;i++){
if(xr>r||(xl<=mid&&p[xl].x<p[xr].x))tmp[i]=p[xl++];elsetmp[i]=p[xr++]; }for(int i=l;i<=r;i++)p[i]=tmp[i];
}
int main(){
memset(dp,0x3f,sizeof dp);SF("%d",&n);for(int i=1;i<=n;i++)SF("%lld",&h[i]);for(int i=1;i<=n;i++){
SF("%lld",&w[i]);pre[i]=pre[i-1]+w[i];}for(int i=1;i<=n;i++){
p[i].id=i;p[i].x=h[i]; }sort(p+1,p+1+n,sort_by_x);dp[1]=0;CDQ(1,n);PF("%lld",dp[n]);
}
/* 6 3 8 7 1 6 6 0 -1 9 1 2 0 */