线段树优化dp水题

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e4 + 10, inf = 2147483647;
int n, k;
int d[N], c[N], s[N], w[N], p[N], f[110][N];

struct Node {
    int mn, tag;
} tr[N << 2];

void pushup(int u) {
    tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn);
}

void pushdown(int u) {
    if (tr[u].tag) {
        tr[u << 1].tag += tr[u].tag;
        tr[u << 1 | 1].tag += tr[u].tag;
        tr[u << 1].mn += tr[u].tag;
        tr[u << 1 | 1].mn += tr[u].tag;
        tr[u].tag = 0;
    }
}

void reset(int u, int l, int r) {
    tr[u].mn = tr[u].tag = 0;
    if (l == r) return;
    int mid = l + r >> 1;
    reset(u << 1, l, mid), reset(u << 1 | 1, mid + 1, r);
}

void modify(int u, int l, int r, int s, int t, int v) {
    if (s > t) return;
    if (s <= l && r <= t) {
        tr[u].tag += v;
        tr[u].mn += v;
        return;
    }
    pushdown(u);
    int mid = l + r >> 1;
    if (s <= mid) modify(u << 1, l, mid, s, t, v);
    if (t > mid) modify(u << 1 | 1, mid + 1, r, s, t, v);
    pushup(u);
}

int query(int u, int l, int r, int s, int t) {
    if (s > t) return 0;
    if (s <= l && r <= t) return tr[u].mn;
    pushdown(u);
    int mid = l + r >> 1;
    if (s > mid) return query(u << 1 | 1, mid + 1, r, s, t);
    if (t <= mid) return query(u << 1, l, mid, s, t);
    return min(query(u << 1, l, mid, s, t), query(u << 1 | 1, mid + 1, r, s, t));
}

bool cmp(int x, int y) {
    return d[x] + s[x] < d[y] + s[y];
}

signed main() {
    scanf("%lld%lld", &n, &k);
    d[0] = -inf;
    for (int i = 2; i <= n; i ++ ) scanf("%lld", &d[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%lld", &c[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%lld", &s[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%lld", &w[i]);
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    sort(p + 1, p + n + 1, cmp);
    d[++ n] = inf;
    for (int i = 1; i <= k + 1; i ++ ) {
        reset(1, 0, n);
        if (i > 1) modify(1, 0, n, 0, 0, inf);
        int g = 0;
        for (int j = 1; j <= n; j ++ ) {
            while (d[p[g + 1]] + s[p[g + 1]] < d[j] && d[j - 1] <= d[p[g + 1]] + s[p[g + 1]]) {
                g ++ ;
                int pos = lower_bound(d, d + n + 1, d[p[g]] - s[p[g]]) - d - 1;
                modify(1, 0, n, 0, pos, w[p[g]]);
            }
            modify(1, 0, n, j, j, f[i - 1][j]);
            if (i == 1) modify(1, 0, n, j, j, inf);
            f[i][j] = query(1, 0, n, 0, j - 1) + c[j];
        }
    }
    int ans = inf;
    for (int i = 1; i <= k + 1; i ++ ) ans = min(ans, f[i][n]);
    printf("%lld\n", ans);
    return 0;
}