对序列切割问题，令 $f[i]=\smash{\displaystyle\min_{0 \le j \le i-1}} F(j, i)$，即 $1$ 到 $i$ 的最优解

$F(j, i) = f[j] + w(j, i)$ 其中 $w(j, i)$ 表示 $j+1$ 到 $i$ 作为一段的代价

若对所有 $j<i$ 有 $w(j,i+1) - w(j,i) \le w(j-1,i+1) - w(j-1,i)$ (四边形不等式)，即可使用此优化 (所以叫四边形不等式优化)

这是因为若四边形不等式满足，则

$$ (f[j] + w(j,i+1)) - (f[j] + w(j,i)) \le (f[j-1] + w(j-1,i+1)) - (f[j-1]+w(j-1,i)) $$ $$ F[j][i+1] - F[j][i] \le F[j-1][i+1] - F[j-1][i] $$ $$ F[j_{大}][i+1] - F[j_{大}][i] \le F[j_{小}][i+1] - F[j_{小}][i] $$

于是如果 $ F[j_{大}][i] \le F[j_{小}][i] $

那对于所有 $ i' > i $ 有 $ F[j_{大}][i'] \le F[j_{小}][i'] $ (*)

(*)就是强化版决策单调性

令 $ pre[i] $ 表示 $ f[i] $ 的决策

那么 $ pre[i] $ 不降就是普通的决策单调性(**)，它可以由(*)得出

用 $ Info $ 合并 $ pre $ 数组中一段相同的值，并用队列维护 $ Info $

$ f[i] $ 求出后就从右到左看它能更新哪些 $ Info $，如果能整个更新，就把这块丢掉，否则就在第一个不能整块更新的块里二分，正确性由(*)和(**)保证


struct Info {
    int l, r, pre;
} q[N];

struct Opt {
    ll val, pre;
} f[N];

ll F(int j, int i) {
    // 具体问题具体分析
}

int search(Info x, int i) {
    int l = x.l;
    int r = x.r;
    int ans = r + 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (F(i, mid) <= F(x.pre, mid)) {
            ans = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    return ans;
}

void DP() {
    q[1] = (Info){1, n, 0};
    int l = 1, r = 2;
    for (int i = 1; i <= n; i++) {
        while (q[l].r < i) l++;
        int j = q[l].pre;
        f[i] = (Opt){F(j, i), j};
        q[l].l = i + 1;
        if (q[l].r == i) l++;
        while (l < r && F(i, q[r-1].l) <= F(q[r-1].pre, q[r-1].l)) r--;
        int pos = i + 1;
        if (l < r) {
            pos = search(q[r-1], i);
            q[r-1].r = pos - 1;
        }
        if (pos > n) continue;
        q[r++] = (Info){pos, n, i};
    }
    printf("%lld\n", f[n].val);
}