李超线段树

WA #5,10,16,17,19

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    char ch=getchar();int x=0;bool f=1;
    while(ch<'0'||'9'<ch){if(ch=='-')f=0;ch=getchar();}
    while('0'<=ch&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f?x:-x;
}
const int N=1e5+2,H=1e6+2,inf=0x3f3f3f3f3f3f3f3f;
int n,h[N],w[N],f[N];
inline int pf(const int x){return x*x;}
struct line{
    int k,b;
};
vector<line>vt;
int cmp(int x,int y){
    if(x>y)return 1;
    else if(x<y)return -1;
    else return 0;
}
int calc(int id,int x){return vt[id].k*x+vt[id].b;}
#define ls(x) tree[x].l
#define rs(x) tree[x].r
struct Tree{
    int l,r,val;
}tree[N<<4];
int root,cnt;
void update(int l,int r,int &k,int v){
    if(!k)k=++cnt;
    int mid=(l+r)>>1;
    int val=cmp(calc(v,mid),calc(tree[k].val,mid));
    if(val==1||(!val&&tree[k].val>v))swap(tree[k].val,v);
    int lval=cmp(calc(v,l),calc(tree[k].val,l));
    int rval=cmp(calc(v,r),calc(tree[k].val,r));
    if(lval==1||(!lval&&tree[k].val>v))update(l,mid,ls(k),v);
    if(rval==1||(!rval&&tree[k].val>v))update(mid+1,r,rs(k),v);
}
int query(int l,int r,int &k,int x){
    if(!k)return 0;
    if(l==r)return calc(tree[k].val,x);
    int mid=(l+r)>>1;
    if(x<=mid)return max(calc(tree[k].val,x),query(l,mid,ls(k),x));
    else return max(calc(tree[k].val,x),query(mid+1,r,rs(k),x));
}
signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    n=read();vt.push_back({0,-inf});
    for(int i=1;i<=n;i++)h[i]=read();
    for(int i=1;i<=n;i++)w[i]=read()+w[i-1];
    memset(f,0x3f,sizeof(f));f[1]=0;
    vt.push_back({h[1]<<1,w[1]-pf(h[1])});
    update(0,1e6,root,vt.size()-1);
    for(int i=2;i<=n;i++){
        f[i]=-query(0,1e6,root,h[i])+w[i-1]+pf(h[i]);
        vt.push_back({h[i]<<1,-f[i]+w[i]-pf(h[i])});
        update(0,1e6,root,vt.size()-1);
    }
    printf("%lld\n",f[n]);
    return 0;
}