求助斜率优化

#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
const int MAXN = 2e5 + 5;
#define INF (1ll << 60)
int n, h[MAXN], w[MAXN], dp[MAXN], pre[MAXN];
struct Node {
    int id, x, y;
    Node() {}
    Node(int x_, int y_, int id_ = 0) { x = x_, y = y_, id = id_; }
} s[MAXN], tmp[MAXN], que[MAXN];
int he, ta;
bool cmph(Node x, Node y) {
    return h[x.id] < h[y.id];
}
void calc(int i, int j) {
    dp[i] = min(dp[i], dp[j] + (h[i] - h[j]) * (h[i] - h[j]) + pre[i - 1] - pre[j]);
}
void Merge(int l, int r) {
    int mid = (l + r) >> 1, i = l, j = mid + 1, tot = l;
    while (i <= mid && j <= r) {
        if (s[i].x < s[j].x || (s[i].x == s[j].x && s[i].y < s[j].y)) tmp[tot++] = s[i++];
        else tmp[tot++] = s[j++];
    }
    while (i <= mid) tmp[tot++] = s[i++];
    while (j <= r) tmp[tot++] = s[j++];
    for (int i = l; i <= r; i++) s[i] = tmp[i];
}
void Solve(int l, int r) {
    if (l == r) {
        s[l].y = dp[l] - pre[l] + h[l] * h[l];
        return;
    }
    int mid = (l + r) >> 1, tot1 = l, tot2 = mid + 1;
    for (int i = l; i <= r; i++) (s[i].id <= mid) ? (tmp[tot1++] = s[i]) : (tmp[tot2++] = s[i]);
    for (int i = l; i <= r; i++) s[i] = tmp[i];
    Solve(l, mid);
    he = 1, ta = 0;
    for (int i = l; i <= mid; i++) {
        while (he < ta && (s[i].y - que[ta].y) * (que[ta].x - que[ta - 1].x) <= (que[ta].y - que[ta - 1].y) * (s[i].x - que[ta].x)) ta--;
        que[++ta] = s[i];
    }
    for (int i = mid + 1; i <= r; i++) {
        while (he < ta && que[he + 1].y - que[he].y <= 2 * s[i].x * (que[he + 1].x - que[he].x)) he++;
        calc(s[i].id, que[he].id);
    }
    Solve(mid + 1, r);
    Merge(l, r);
}
signed main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &w[i]);
        pre[i] = pre[i - 1] + w[i];
        s[i].id = i, s[i].x = h[i];
        if (i != 1) dp[i] = INF;
    }
    sort(s + 1, s + 1 + n, cmph);
    Solve(1, n);
    printf("%lld", dp[n]);
    return 0;
}

维护凸包的时候多取了个等号，然后A了。以前没太注意，想问问有什么大问题。