动开线段树的疑惑

这是静态开点线段树，80pts WA

#include <bits/stdc++.h>
#define int long long

using namespace std;
inline int read() {
    int res = 0, f = 1;
    char ch = getchar();
    while (!isdigit (ch)) f = ch == '-' ? -1 : 1, ch = getchar();
    while (isdigit (ch)) res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
    return res * f;
}
const int MAXN = 2e6 + 10, inf = LLONG_MAX;
int n, h[MAXN], w[MAXN], sumw[MAXN], dp[MAXN];
inline int Getx (int p) { return h[p]; }
inline int Getb (int p) { return dp[p] + h[p] * h[p] - sumw[p]; }
inline int Getk (int p) { return -2 * h[p]; }
struct line {
    int k, b;
    line (int k = 0, int b = 0):k(k), b(b){};
    int Getfx (int x) { return k * x + b; }
};
struct Ayaka {
    int l, r;
    line ln;
    bool isCover;
    Ayaka (int l, int r, line ln, bool isCover):l(l), r(r), ln(ln), isCover(isCover){};
    Ayaka (){}
}seg[MAXN << 2];

void Build (int l, int r, int rt) {
    seg[rt] = Ayaka (l, r, line(), false);
    if (l == r) return;
    int mid = l + r >> 1;
    Build (l, mid, rt << 1), Build (mid + 1, r, rt << 1 | 1);
    return;
}

void Modify (int rt, line lnx) {
    int l = seg[rt].l, r = seg[rt].r;
    int lpos = seg[rt].ln.Getfx (l), rpos = seg[rt].ln.Getfx (r);
    int tmpLpos = lnx.Getfx (l), tmpRpos = lnx.Getfx (r);
    if (!seg[rt].isCover)
        seg[rt].isCover = true, seg[rt].ln = lnx;
    else if (tmpLpos <= lpos && tmpRpos <= rpos) seg[rt].ln = lnx; /* 原线段完全在新线段之下 */
    else if (tmpLpos <= lpos || tmpRpos <= rpos) {
        int mid = l + r >> 1;
        if (seg[rt].ln.Getfx (mid) > lnx.Getfx (mid)) swap (seg[rt].ln, lnx); /* 如果新线段在 mid 处比原线段小则交换 */
        if (seg[rt].ln.Getfx (l) > lnx.Getfx (l)) Modify (rt << 1, lnx); /* 右侧一定更优递归左侧 */
        else Modify (rt << 1 | 1, lnx); /* 左侧一定更优递归右侧 */
    }
    return;
}

int query (int pos, int rt) {
    int l = seg[rt].l, r = seg[rt].r;
    int tmpVal = seg[rt].ln.Getfx (pos);
    if (l == r) return tmpVal;
    int mid = l + r >> 1;
    if (pos <= mid)
        tmpVal = min (tmpVal, query (pos, rt << 1));
    else
        tmpVal = min (tmpVal, query (pos, rt << 1 | 1));
    return tmpVal;
}

signed main() {
    n = read(), Build (1, 2e6, 1);
    for (int i = 1; i <= n; i ++) h[i] = read();
    for (int i = 1; i <= n; i ++)
        w[i] = read(), sumw[i] = sumw[i - 1] + w[i];
    Modify (1, line (0, inf));
    Modify (1, line (Getk (1), Getb (1)));
    for (int i = 2; i <= n; i ++) {
        dp[i] = query (Getx (i), 1) + h[i] * h[i] + sumw[i - 1];
        Modify (1, line (Getk (i), Getb (i)));
    }
    printf ("%lld\n", dp[n]);
    return 0;
}

写成动态开点就过了

#include <bits/stdc++.h>
#define int long long

using namespace std;
inline int read() {
    int res = 0, f = 1;
    char ch = getchar();
    while (!isdigit (ch)) f = ch == '-' ? -1 : 1, ch = getchar();
    while (isdigit (ch)) res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
    return res * f;
}
const int MAXN = 1e6 + 10, inf = LLONG_MAX;
int n, h[MAXN], w[MAXN], sumw[MAXN], dp[MAXN], ind, rt;
inline int Getx (int p) { return h[p]; }
inline int Getb (int p) { return dp[p] + h[p] * h[p] - sumw[p]; }
inline int Getk (int p) { return -2 * h[p]; }
struct line {
    int k, b;
    line (int k = 0, int b = 0):k(k), b(b){};
    int Getfx (int x) { return k * x + b; }
};
struct Ayaka {
    int lson, rson;
    line ln;
    bool isCover;
}seg[MAXN << 2];

void Modify (int &rt, line lnx, int l, int r) {
    if (!rt) rt = ++ ind;
    int lpos = seg[rt].ln.Getfx (l), rpos = seg[rt].ln.Getfx (r);
    int tmpLpos = lnx.Getfx (l), tmpRpos = lnx.Getfx (r);
    if (!seg[rt].isCover)
        seg[rt].isCover = true, seg[rt].ln = lnx;
    else if (tmpLpos <= lpos && tmpRpos <= rpos) seg[rt].ln = lnx; /* 原线段完全在新线段之下 */
    else if (tmpLpos <= lpos || tmpRpos <= rpos) {
        int mid = l + r >> 1;
        if (seg[rt].ln.Getfx (mid) > lnx.Getfx (mid)) swap (seg[rt].ln, lnx); /* 如果新线段在 mid 处比原线段小则交换 */
        if (seg[rt].ln.Getfx (l) > lnx.Getfx (l)) Modify (seg[rt].lson, lnx, l, mid); /* 右侧一定更优递归左侧 */
        else Modify (seg[rt].rson, lnx, mid + 1, r); /* 左侧一定更优递归右侧 */
    }
    return;
}

int query (int pos, int rt, int l, int r) {
    if (!rt) return inf;
    int tmpVal = seg[rt].ln.Getfx (pos);
    if (l == r) return tmpVal;
    int mid = l + r >> 1;
    if (pos <= mid)
        tmpVal = min (tmpVal, query (pos, seg[rt].lson, l, mid));
    else
        tmpVal = min (tmpVal, query (pos, seg[rt].rson, mid + 1, r));
    return tmpVal;
}

signed main() {
    n = read();
    for (int i = 1; i <= n; i ++) h[i] = read();
    for (int i = 1; i <= n; i ++)
        w[i] = read(), sumw[i] = sumw[i - 1] + w[i];
    Modify (rt, line (0, inf), 1, 1e6);
    Modify (rt, line (Getk (1), Getb (1)), 1, 1e6);
    for (int i = 2; i <= n; i ++) {
        dp[i] = query (Getx (i), 1, 1, 1e6) + h[i] * h[i] + sumw[i - 1];
        Modify (rt, line (Getk (i), Getb (i)), 1, 1e6);
    }
    printf ("%lld\n", dp[n]);
    return 0;
}

Why ?

顺带求调第一份代码。