40pts求调，玄关

jimmy916 @ 2024-08-27 22:12:17

#include <iostream>
#include <iostream>
#include <cstdio>
#define lc (x<<1)
#define rc (x<<1)|1
#define int long long

using namespace std;

const int N = 1e6 + 1, Inf = 1000000000000000000ll;

int n, m;
int a[N];

struct tree {
    int l, r;
    int val;
    int lazy_add;
    int lazy_set;
} t[N << 2];

void pushup(int x) {
    t[x].val = max(t[lc].val, t[rc].val);
    return;
}

void maketag(int x, int k, int type) {
    if (type) {
        t[x].val += k;
        if (t[x].lazy_set != Inf)
            t[x].lazy_set += k;
        else
            t[x].lazy_add += k;
    } else {
        t[x].val = t[x].lazy_set = k;
        t[x].lazy_add = 0;
    }
    return;
}

void pushdown(int x) {
    if (t[x].lazy_set != Inf) {
        maketag(lc, t[x].lazy_set, 0);
        maketag(rc, t[x].lazy_set, 0);
        t[x].lazy_set = Inf;
    } else if (t[x].lazy_add) {
        maketag(lc, t[x].lazy_add, 1);
        maketag(rc, t[x].lazy_add, 1);
        t[x].lazy_add = 0;
    }
    return;
}

void build(int l, int r, int x) {
    t[x].l = l, t[x].r = r, t[x].lazy_set = Inf;
    if (l == r) {
        t[x].val = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, lc), build(mid + 1, r, rc);
    pushup(x);
    return;
}

void update(int l, int r, int k, int type, int x) {
    if (t[x].l > r || t[x].r < l)
        return;
    if (l <= t[x].l && t[x].r <= r) {
        maketag(x, k, type);
        return;
    }
    pushdown(x);
    update(l, r, k, type, lc), update(l, r, k, type, rc);
    pushup(x);
    return;
}

int ask(int l, int r, int x) {
    if (t[x].l > r || t[x].r < l)
        return 0;
    if (l <= t[x].l && t[x].r <= r)
        return t[x].val;
    pushdown(x);
    int maxn = max(ask(l, r, lc), ask(l, r, rc));
    pushup(x);
    return maxn;
}

signed main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        scanf("%d", a + i);
    build(1, n, 1);
    for (int i = 1; i <= m; i ++ ) {
        int op;
        scanf("%d", &op);
        if (op == 1 || op == 2) {
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            update(l, r, x, (op - 1), 1);
        } else if (op == 3) {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", ask(l, r, 1));
        }
    }
    return 0;
}

by jimmy916 @ 2024-08-28 09:31:11

50pts了

#include <iostream>
#include <cstdio>
#define lc (x<<1)
#define rc (x<<1)|1
#define int long long

using namespace std;

const int N = 1e6 + 1, Inf = 1000000000000000000ll;

int n, m;
int a[N];

struct tree {
    int l, r;
    int val;
    int lazy_add;
    int lazy_set;
} t[N << 2];

void pushup(int x) {
    t[x].val = max(t[lc].val, t[rc].val);
    return;
}

void maketag(int x, int k, int type) {
    if (type) {
        t[x].val += k;
        if (t[x].lazy_set != Inf)
            t[x].lazy_set += k;
        else
            t[x].lazy_add += k;
    } else {
        t[x].val = t[x].lazy_set = k;
        t[x].lazy_add = 0;
    }
    return;
}

void pushdown(int x) {
    if (t[x].lazy_set != Inf) {
        maketag(lc, t[x].lazy_set, 0);
        maketag(rc, t[x].lazy_set, 0);
        t[x].lazy_set = Inf;
        t[x].lazy_add = 0;
    } else if (t[x].lazy_add) {
        maketag(lc, t[x].lazy_add, 1);
        maketag(rc, t[x].lazy_add, 1);
        t[x].lazy_add = 0;
    }
    return;
}

void build(int l, int r, int x) {
    t[x].l = l, t[x].r = r, t[x].lazy_set = Inf;
    if (l == r) {
        t[x].val = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, lc), build(mid + 1, r, rc);
    pushup(x);
    return;
}

void update(int l, int r, int k, int type, int x) {
    if (t[x].l > r || t[x].r < l)
        return;
    if (l <= t[x].l && t[x].r <= r) {
        maketag(x, k, type);
        return;
    }
    pushdown(x);
    update(l, r, k, type, lc), update(l, r, k, type, rc);
    pushup(x);
    return;
}

int ask(int l, int r, int x) {
    if (t[x].l > r || t[x].r < l)
        return 0;
    if (l <= t[x].l && t[x].r <= r)
        return t[x].val;
    pushdown(x);
    int maxn = max(ask(l, r, lc), ask(l, r, rc));
    pushup(x);
    return maxn;
}

signed main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i ++ )
        scanf("%lld", a + i);
    build(1, n, 1);
    for (int i = 1; i <= m; i ++ ) {
        int op;
        scanf("%lld", &op);
        if (op == 1 || op == 2) {
            int l, r, x;
            scanf("%lld%lld%lld", &l, &r, &x);
            update(l, r, x, (op - 1), 1);
        } else if (op == 3) {
            int l, r;
            scanf("%lld%lld", &l, &r);
            printf("%lld\n", ask(l, r, 1));
        }
    }
    return 0;
}