求调，斜率优化splay维护动态凸包

最后一个点开O2TLE，不开MLE，无法理解，已经写了一天了

#include<iostream>
#include<algorithm>
#include<cstring>

#define re register
#define int long long

using namespace std;

const double INF=1e16;
const double eps=1e-10;
const int N=2e5+10;

int n;
int h[N];
int s[N];
int f[N];

int root;
int ch[N][2], fa[N];
double lk[N], rk[N];
int xp[N];
int yp[N];

inline int read()
{
    register int x=0,w=1;
    register char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-'){ch=getchar();w=-1;  }
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();   }
    return x*w;
}

int get(int x){ return x==ch[fa[x]][1]; }

inline int X(int x){ return h[x]; }
inline int Y(int x){ return f[x] + h[x]*h[x] - s[x]; }
inline int K(int x){ return 2*h[x]; }

inline int get_ans(int i,int j){
    return f[j] + h[i]*h[i] + h[j]*h[j] - 2*h[i]*h[j] + s[i-1]-s[j];
}

inline double slope(int i, int j) {
    if (xp[i]==xp[j]) return yp[i] < yp[j] ? INF : -INF;
    return ((yp[i] - yp[j])*1.0) / ((xp[i] - xp[j])*1.0);
}

inline void rotate(int x){
    int y=fa[x], z=fa[y], k=get(x);
    ch[y][k]=ch[x][k^1];
    if(ch[x][k^1]) fa[ch[x][k^1]]=y;
    ch[x][k^1]=y;
    fa[y]=x;
    fa[x]=z;
    if(z) ch[z][y==ch[z][1]]=x;
    return ;
}

inline void splay(int x,int goal){
    for(re int f;f=fa[x],f!=goal;rotate(x)){
        if(fa[f]!=goal) rotate(get(x)==get(f)?f:x);
    }
    if(goal==0) root=x;
    return ;
}

inline int getlast(int x){
    int ans=0;
    for(re int y=ch[x][0]; y; ){
        if(slope(y,x)+eps >= lk[y]) ans=y,y=ch[y][1];
        else y=ch[y][0];
    }
    return ans;
}

inline int getnext(int x){
    int ans=0;
    for(re int y=ch[x][1]; y; ){
        if(slope(x,y) <= rk[y]+eps) ans=y,y=ch[y][0];
        else y=ch[y][1];
    }
    return ans;
}

inline int query(int x, double k){
    if (lk[x] <= k+eps && k <= rk[x]+eps) return x;
    if (k+eps >= rk[x]) return query(ch[x][1],k);
    else return query(ch[x][0],k);
}

inline void check(int &rt,int x){
    splay(x,0);
    if(ch[root][0]){//左边有子树 
        int y=getlast(x);
        splay(y,x);
        ch[y][1]=0;
        rk[y]=lk[x]=slope(y,x);
    }
    else{//没有左子树 
        lk[x]=-INF;
    }

    if(ch[root][1]){
        int y=getnext(x);
        splay(y,x);
        ch[y][0]=0;
        rk[x]=lk[y]=slope(x,y);
    }
    else{
        rk[x]=INF;
    }

    if(lk[x]>=rk[x]+eps){
        rt=ch[x][0];
        fa[ch[rt][1]=ch[x][1]]=rt;
        fa[rt]=0;
        rk[rt]=lk[ch[rt][1]]=slope(rt,ch[rt][1]);
    }
    return ;
}

inline void insert(int &x,int f,int id){
    if(!x){//新建节点
        fa[x=id]=f;
        return ;
    }
    else{
        if(xp[x]<=xp[id]) insert(ch[x][1],x,id);//往右子树插 
        else insert(ch[x][0],x,id);
    } 
}

signed main(){

    cin>>n;
    for(re int i=1;i<=n;++i) h[i]=read();
    for(re int i=1;i<=n;++i) s[i]=read(),s[i]+=s[i-1];

    f[1]=0;
    xp[1]=h[1];
    yp[1]=f[1]-s[1]+h[1]*h[1];
    f[2]=(h[2]-h[1])*(h[2]-h[1]);
    xp[2]=h[2];
    yp[2]=f[2]-s[2]+h[2]*h[2];

    //插入并重新维护下凸壳 
    insert(root,0,1), check(root,1);
    insert(root,0,2), check(root,2);
    for(re int i=3;i<=n;++i){
        int j=query(root,K(i));
        f[i]=f[j] + h[i]*h[i] + h[j]*h[j] - 2*h[i]*h[j] + s[i-1]-s[j];
        xp[i]=h[i];
        yp[i]=f[i]+h[i]*h[i]-s[i];
        insert(root,0,i);
        check(root,i);

    } 
    cout<<f[n]<<endl;
    return 0;
}