CDQ 85pts 求助

/*
 * Date: 01/12/23 13:51
 * Time Spent: 1:48:14
 * Solution:
     1. dp[i] = min{dp[j] + (h[i]-h[j])^2 + w[i-1] - w[j]}
        dp[i] = min{dp[j] + h[i]^2-h[i]*h[j]+h[j]^2 + w[i-1] - w[j]}
            dp[i] - (h[i]*h[i] + w[i-1]) = dp[j] - w[j] + h[j]*h[j] - 2*h[i]*h[j]
            ~~~~~~~~~~~~~b~~~~~~~~~~~~~~   ~~~~~~~~~~~~y~~~~~~~~~~~   ~~~k~~ ~x~
        <=> y = k*x + b
 * Summhry:
     1. RAW55 没有跟自己取 min。。。
     2. 好像终于把斜率优化理解透了（好耶！
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// #define int long long
#define double long double
const int N = 1e5 + 5;
const ll inf = 1e18;
int n, h[N], st[N]; ll w[N], dp[N];
struct node {
    ll x, y, id;
    void upd (ll _dp) {
        x = h[id];
        y = _dp - w[id] + 1ll*h[id]*h[id];
    }
} a[N], tmp[N];
double slope (int p, int q) {
    if (a[q].x == a[p].x) return a[p].y > a[p].y ? -1e20 : 1e20;
    return (double)(a[q].y - a[p].y) / (a[q].x - a[p].x);
}
ll slope (int p) {
    return 2ll*h[a[p].id];
}
void CDQ (int l, int r) {
    if (l == r) return a[l].upd(dp[a[l].id]);
    int mid = l + r >> 1;
    stable_partition(a+l, a+r+1, [&](node p){ return p.id <= mid; });
    CDQ(l, mid);
    st[0] = 0;
    // printf("[%d,%d]\n", l, r);
    for (int i = l; i <= mid; i++) {
        while (st[0] >= 2 && slope(st[st[0]-1], st[st[0]]) >= slope(st[st[0]-1], i)) st[0]--;
        st[++st[0]] = i;
    }
    int t = 1;  // !
    for (int k = mid+1; k <= r; k++) {
        while (t < st[0] && slope(st[t], st[t+1]) < slope(k)) t++;
        // int i = a[k].id, j = a[st[t]].id;  // Both OK
        // dp[i] = min(dp[i], dp[j] + 1ll*(h[i]-h[j])*(h[i]-h[j]) + w[i-1] - w[j]);
        int i = a[k].id, j = st[t];
        dp[i] = min(dp[i], a[j].y - slope(k)*a[j].x + (1ll*h[i]*h[i] + w[i-1]));
    }
    CDQ(mid+1, r);
    inplace_merge(a+l, a+mid+1, a+r+1, [&](node p, node q){ return p.x < q.x; });
    // inplace_merge(a+l, a+mid+1, a+r+1, [&](node p, node q){ return p.x ^ q.x ? p.x < q.x : p.y > q.y; });
}
signed main () {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> w[i], w[i] += w[i-1];
    for (int i = 1; i <= n; i++) a[i].id = i, a[i].upd(dp[i]=inf);
    a[1].upd(dp[1]=0);
    stable_sort(a+1, a+n+1, [&](node p, node q){ return h[p.id] < h[q.id]; });
    CDQ(1, n);
    cout << dp[n];
    return 0;
}

Record

问题好像是跟 CDQ 最后归并的时候有关。

如果把：

inplace_merge(a+l, a+mid+1, a+r+1, [&](node p, node q){ return p.x < q.x; });

改成：

inplace_merge(a+l, a+mid+1, a+r+1, [&](node p, node q){ return p.x <= q.x; });

就只有 80pts 了 QAQ