李超树 45pts 求助

#include <bits/stdc++.h>
#define int long long
#define lx (x * 2)
#define rx (x * 2 + 1)
#define mid ((l + r) >> 1)

using namespace std;

int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while(!isdigit(ch))
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int N = 100000, A = 1000000;
const double eps = 1e-8, INF = 1e18 + 114514;
int n;
int h[N + 5], w[N + 5], s[N + 5];

void init()
{
    n = read();
    for(int i = 1; i <= n; i++)
    {
        h[i] = read();
    }
    for(int i = 1; i <= n; i++)
    {
        w[i] = read();
    }
    for(int i = 1; i <= n; i++)
    {
        s[i] = s[i - 1] + w[i];
    }
}

int cmp(double x, double y)
{
    if(x - y > eps)
    {
        return 1;
    }
    if(y - x > eps)
    {
        return -1;
    }
    return 0;
}
struct Seg
{
    double k, b;
    double calc(int x)
    {
        return k * x + b;
    }
}seg[N + 5];
struct Tr
{
    int mnp;
}tr[A * 4 + 5];
void add(int x, int l, int r, int s, int t, int id)
{
    if(l >= s && r <= t)
    {
//      printf("%lld %lld\n", l, r);
        if(tr[x].mnp == 0)
        {
            tr[x].mnp = id;
            return;
        }
        if(cmp(seg[id].calc(mid), seg[tr[x].mnp].calc(mid)) <= 0)
        {
            swap(id, tr[x].mnp);
        }       
        if(cmp(seg[tr[x].mnp].calc(l), seg[id].calc(l)) <= 0 && cmp(seg[tr[x].mnp].calc(r), seg[id].calc(r)) <= 0)
        {
            return;
        }
        if(l == r)
        {
            return;
        }
        if(cmp(seg[id].calc(l), seg[tr[x].mnp].calc(l)) <= 0)
        {
            add(lx, l, mid, s, t, id);
        }
        if(cmp(seg[id].calc(r), seg[tr[x].mnp].calc(r)) <= 0)
        {
            add(rx, mid + 1, r, s, t, id);
        }
        return;
    }
    if(s <= mid)
    {
        add(lx, l, mid, s, t, id);
    }
    if(t > mid)
    {
        add(rx, mid + 1, r, s, t, id);
    }
}
double ask(int x, int l, int r, int s)
{
    if(l == r)
    {
        if(tr[x].mnp == 0)
        {
            return INF;
        }
        else
        {
            return seg[tr[x].mnp].calc(s);
        }
    }
    double ret;
    if(tr[x].mnp == 0)
    {
        ret = INF;
    }
    else
    {
        ret = seg[tr[x].mnp].calc(s);
    }
    if(s <= mid)
    {
        ret = min(ret, ask(lx, l, mid, s));
    }
    else
    {
        ret = min(ret, ask(rx, mid + 1, r, s));
    }
    return ret;
}

int f[N + 5];
void solve()
{
    f[1] = 0;
    seg[1] = {-(double)2 * h[1], ((double)f[1] + h[1] * h[1] - s[1])};
    add(1, 0, A, 0, A, 1);
    for(int i = 2; i <= n; i++)
    {
        f[i] = (int)((double)h[i] * h[i] + s[i - 1] + ask(1, 0, A, h[i]) + 0.5);
        seg[i] = {-(double)2 * h[i], ((double)f[i] + (double)h[i] * h[i] - s[i])};
        add(1, 0, A, 0, A, i);
    }
    printf("%lld", f[n]);
}

signed main()
{
//  freopen(".out", "r", stdin);
//  freopen(".out", "w", stdout);
    init();
    solve();
    return 0;
}