50pts 后五个点没过,dalao求调

P1253 扶苏的问题

I_love_LPN_Forever @ 2022-08-09 10:50:51


#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 5;
const int INF = LLONG_MAX;
struct node {
    int l, r, mx, lz1, lz2;
} t[maxn << 2];
int n, m, a[maxn];
void push_down(int i) {
    if (t[i].lz1 != INF) {
        t[i * 2].mx = t[i].lz1;
        t[i * 2 + 1].mx = t[i].lz1;
        t[i * 2].lz1 = t[i].lz1;
        t[i * 2 + 1].lz1 = t[i].lz1;
        t[i].lz1 = INF;
    }
    if (t[i].lz2) {
        t[i * 2].mx += t[i].lz2;
        t[i * 2 + 1].mx += t[i].lz2;
        t[i * 2].lz2 += t[i].lz2;
        t[i * 2 + 1].lz2 += t[i].lz2;
        t[i].lz2 = 0;
    }
}
void build(int i, int l, int r) {
    t[i].l = l, t[i].r = r, t[i].lz1 = INF;
    if (l == r) {
        t[i].mx = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(i * 2, l, mid);
    build(i * 2 + 1, mid + 1, r);
    t[i].mx = max(t[i * 2].mx, t[i * 2 + 1].mx);
}
void upd1(int i, int l, int r, int d) {
    if (t[i].l >= l && t[i].r <= r) {
        t[i].lz1 = d;
        t[i].mx = d;
        return;
    }
    push_down(i);
    if (t[i * 2].r >= l) upd1(i * 2, l, r, d);
    if (t[i * 2 + 1].l <= r) upd1(i * 2 + 1, l, r, d);
    t[i].mx = max(t[i * 2].mx, t[i * 2 + 1].mx);
}
void upd2(int i, int l, int r, int d) {
    if (l <= t[i].l && t[i].r <= r) {
        t[i].mx += d;
        t[i].lz2 += d;
        return;
    }
    push_down(i);
    if (t[i * 2].r >= l) upd2(i * 2, l, r, d);
    if (t[i * 2 + 1].l <= r) upd2(i * 2 + 1, l, r, d);
    t[i].mx = max(t[i * 2].mx, t[i * 2 + 1].mx);
}
int query(int i, int l, int r) {
    if (l <= t[i].l && t[i].r <= r) {
        return t[i].mx;
    }
    push_down(i);
    int ans = -1;
    if (t[i * 2].r >= l) ans = max(ans, query(i * 2, l, r));
    if (t[i * 2 + 1].l <= r) ans = max(ans, query(i * 2 + 1, l, r));
    return ans;
}
signed main() {
    //freopen("1.in", "r", stdin);
    scanf("%lld %lld", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        int opt, x, y, d;
        scanf("%lld", &opt);
        if (opt == 1) {
            scanf("%lld %lld %lld", &x, &y, &d);
            upd1(1, x, y, d);
        }
        if (opt == 2) {
            scanf("%lld %lld %lld", &x, &y, &d);
            upd2(1, x, y, d);
        }
        if (opt == 3) {
            scanf("%lld %lld", &x, &y);
            printf("%lld\n", query(1, x, y));
        }
    }
}

|