Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 months ago
4.6 kB
2
Indexable
Never
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

using ll = long long;

constexpr int N = 2e5;

int w[N], d[N - 1];

struct segtree {
    struct node {
        ll dp[2][2], id;
        node() {
            dp[0][0] = LLONG_MIN / 4;
            dp[0][1] = LLONG_MIN / 4;
            dp[1][0] = LLONG_MIN / 4;
            dp[1][1] = LLONG_MIN / 4;
            id = -1;
        }

        node(int i) {
            dp[0][0] = 0;
            dp[0][1] = LLONG_MIN / 4;
            dp[1][0] = LLONG_MIN / 4;
            dp[1][1] = d[i] - w[i] - w[i + 1];
            id = i;
        }

        void dbg() {
            debug(id, dp[0][0], dp[0][1], dp[1][0], dp[1][1]);
        }
    };
    int size;
    vector<node> tree;

    void init(int n) {
        size = 1;
        while (size < n) size *= 2;
        tree.assign(2 * size - 1, node());
    }

    node merge(node a, node b) {
        if (b.id == -1) return a;
        if (a.id == -1) return b;
        node res;
        res.dp[0][0] = 0;
        res.id = b.id;
        for (int li = 0; li <= 1; li++) {
            for (int ri = 0; ri <= 1; ri++) {
                if (a.dp[li][ri] == LLONG_MIN / 4) continue;
                for (int lj = 0; lj <= 1; lj++) {
                    for (int rj = 0; rj <= 1; rj++) {
                        if (b.dp[lj][rj] == LLONG_MIN / 4) continue;
                        ll h = a.dp[li][ri] + b.dp[lj][rj];
                        if (ri == 1 && rj == 1) {
                            h += w[a.id + 1];
                        }
                        res.dp[li][rj] = max(h, res.dp[li][rj]);
                    }
                }
            }
        }
        return res;
    }

    void update(int i, int x, int lx, int rx) {
        if (rx - lx == 1) {
            tree[x] = node(i);
        } else {
            int m = (lx + rx) / 2;
            if (i < m) {
                update(i, x * 2 + 1, lx, m);
            } else {
                update(i, x * 2 + 2, m, rx);
            }
            tree[x] = merge(tree[x * 2 + 1], tree[x * 2 + 2]);
        }
        //debug(x, lx, rx);
        //tree[x].dbg();
    }

    void update(int i) {
        update(i, 0, 0, size);
    }

    node get(int l, int r, int x, int lx, int rx) {
        //debug(lx, rx);
        if (lx >= r || rx <= l) {
            return node();
        } else if (lx >= l && rx <= r) {
            //tree[x].dbg();
            //debug(lx, rx);
            return tree[x];
        } else {
            int m = (lx + rx) / 2;
            return merge(get(l, r, x * 2 + 1, lx, m), get(l, r, x * 2 + 2, m, rx));
        }
    }

    ll get(int l, int r, int x) {
        node v = get(l, r, 0, 0, size);
        ll ans = 0;
        for (int li = 0; li <= 1; li++) {
            for (int ri = 0; ri <= 1; ri++) {
                for (int take = 0; take <= 1; take++) {
                    ll h = v.dp[li][ri];
                    if (take) {
                        h += x;
                        if (li == 0) {
                            h -= w[l];
                        }   
                        if (ri == 0) {
                            h -= w[r];
                        }
                    }
                    ans = max(ans, h);
                }
            }
        }
        return max(0LL, ans);
    }
};

void test_case() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }
    for (int i = 0; i < n - 1; i++) {
        cin >> d[i];
    }
    segtree tr;
    tr.init(n - 1);
    for (int i = 0; i < n - 1; i++) {
        tr.update(i);
    }
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int p, x;
            cin >> p >> x;
            p--;
            w[p] = x;
            if (p < n - 1) {
                tr.update(p);
            }
            if (p >= 1) {
                tr.update(p - 1);
            }
        } else if (t == 2) {
            int p, x;
            cin >> p >> x;
            p--;
            d[p] = x;
            tr.update(p);
        } else {
            int l, r, x;
            cin >> l >> r >> x;
            l--; r--;
            cout << tr.get(l, r, x) << '\n';
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        test_case();
    }
    return 0;
}
Leave a Comment