线段树 20pts 求调

P1253 扶苏的问题

littlesnake @ 2024-12-20 21:43:07

rt.赏一关

# include <bits/stdc++.h>
# define ll long long
# define N 1000010
# define inf 1000000000000000000ll

using namespace std;

ll a[N], w[N * 4], lzy1[N * 4], lzy2[N * 4];
ll k;
int n, m, op, x, y;

// 建树
void pushup (int u) {
    w[u] = max (w[u * 2], w[u * 2 + 1]);
}

void build (int u, int L, int R) {
    if (L == R) {
        w[u] = a[L];
        lzy2[u] = inf;
        return ;
    }
    int mid = (L + R) / 2;
    build (u * 2, L, mid);
    build (u * 2 + 1, mid + 1, R);
    pushup (u);
}

// 单点查询
ll query1 (int u, int L, int R, int p) {
    if (L == R) return w[u];
    else {
        int mid = (L + R) / 2;
        if (mid >= p) return query1 (u * 2, L, mid, p);
        else return query1 (u * 2 + 1, mid + 1, R, p);
    }
}

// 单点修改
void update1 (int u, int L, int R, int p, ll x) {
    if (L == R) w[u] = x;
    else {
        int mid = (L + R) / 2;
        if (mid >= p) update1 (u * 2, L, mid, p, x);
        else update1 (u * 2 + 1, mid + 1, R, p, x);
        pushup (u);
    }
}

// 区间查询
bool InRange (int L, int R, int l, int r) {
    return (l <= L) && (R <= r);
}

bool OutofRange (int L, int R, int l, int r) {
    return (L > r) || (R < l);
}

ll query1 (int u, int L, int R, int l, int r) {
    if (InRange (L, R, l, r)) return w[u];
    else if (! OutofRange (L, R, l, r)) {
        int mid = (L + R) / 2;
        return query1 (u * 2, L, mid, l, r) + query1 (u * 2 + 1, mid + 1, R, l, r);
    } else return 0;
}

// 区间修改
void maketag (int u, ll x, int type) {
    if (type == 1) {
        lzy1[u] = 0;
        lzy2[u] = x;
        w[u] = x;
    } else {
        if (lzy2[u] == inf) lzy1[u] += x;
        else lzy2[u] += x;
        w[u] += x;
    }
}

void pushdown (int u, int L, int R) {
    if (lzy2[u] == inf) {
        maketag (u * 2, lzy1[u], 2);
        maketag (u * 2 + 1, lzy1[u], 2);
        lzy1[u] = 0;
    } else {
        maketag (u * 2, lzy2[u], 1);
        maketag (u * 2 + 1, lzy2[u], 1);
        lzy2[u] = inf;
    }
}

ll query (int u, int L, int R, int l, int r) {
    if (InRange (L, R, l, r)) return w[u];
    pushdown (u, L, R);
    int mid = (L + R) / 2;
    ll ans = -inf;
    if (l <= mid) ans = max (ans, query (u * 2, L, mid, l, r));
    if (r > mid) ans = max (ans, query (u * 2 + 1, mid + 1, R, l, r));
    return ans;
}

void update (int u, int L, int R, int l, int r, ll x, int type) {
    pushdown (u, L, R);
    if (InRange (L, R, l, r)) {
        maketag (u, x, type);
        return ;
    }
    int mid = (L + R) / 2;
    if (l <= mid) update (u * 2, L, mid, l, r, x, type);
    if (r > mid) update (u * 2 + 1, mid + 1, R, l, r, x, type);
    pushup (u);
}

int main () {

    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) scanf ("%lld", &a[i]);
    build (1, 1, n);
    for (int i = 1; i <= m; i ++) {
        scanf ("%d", &op);
        if (op == 1) {
            scanf ("%d%d%lld", &x, &y, &k);
            update (1, 1, n, x, y, k, 1);
        } else if (op == 2) {
            scanf ("%d%d%lld", &x, &y, &k);
            update (1, 1, n, x, y, k, 2);
        } else if (op == 3) {
            scanf ("%d%d", &x, &y);
            printf ("%lld\n", query (1, 1, n, x, y));
        }
    }

    return 0;

}

by ljcnoi @ 2024-12-20 21:53:26

@littlesnake你把覆盖的标记传下去是，要把加标记清空

by littlesnake @ 2024-12-20 22:01:00

@ljcnoi 能详细一说吗

by littlesnake @ 2024-12-21 10:04:31

50 分

# include <bits/stdc++.h>
# define ll long long
# define N 1000010
# define inf 1000000000000000000ll

using namespace std;

ll a[N], w[N * 4], lzy1[N * 4], lzy2[N * 4];
ll k;
int n, m, op, x, y;

// 建树
void pushup (int u) {
    w[u] = max (w[u * 2], w[u * 2 + 1]);
}

void build (int u, int L, int R) {
    if (L == R) {
        w[u] = a[L];
        lzy2[u] = inf;
        return ;
    }
    int mid = (L + R) / 2;
    build (u * 2, L, mid);
    build (u * 2 + 1, mid + 1, R);
    pushup (u);
}

// 单点查询
ll query1 (int u, int L, int R, int p) {
    if (L == R) return w[u];
    else {
        int mid = (L + R) / 2;
        if (mid >= p) return query1 (u * 2, L, mid, p);
        else return query1 (u * 2 + 1, mid + 1, R, p);
    }
}

// 单点修改
void update1 (int u, int L, int R, int p, ll x) {
    if (L == R) w[u] = x;
    else {
        int mid = (L + R) / 2;
        if (mid >= p) update1 (u * 2, L, mid, p, x);
        else update1 (u * 2 + 1, mid + 1, R, p, x);
        pushup (u);
    }
}

// 区间查询
bool InRange (int L, int R, int l, int r) {
    return (l <= L) && (R <= r);
}

bool OutofRange (int L, int R, int l, int r) {
    return (L > r) || (R < l);
}

ll query1 (int u, int L, int R, int l, int r) {
    if (InRange (L, R, l, r)) return w[u];
    else if (! OutofRange (L, R, l, r)) {
        int mid = (L + R) / 2;
        return query1 (u * 2, L, mid, l, r) + query1 (u * 2 + 1, mid + 1, R, l, r);
    } else return 0;
}

// 区间修改
void maketag (int u, ll x, int type) {
    if (type == 1) {
        lzy1[u] += x;
        w[u] += x;
    } else {
        if (lzy2[u] == inf) lzy1[u] += x;
        else lzy2[u] += x;
        w[u] += x;
    }
}

void pushdown (int u, int L, int R) {
    if (lzy2[u] < inf) {
        maketag (u * 2, lzy2[u], 1);
        maketag (u * 2 + 1, lzy2[u], 1);
        lzy2[u] = inf;
    }
    maketag (u * 2, lzy1[u], 2);
    maketag (u * 2 + 1, lzy1[u], 2);
    lzy1[u] = 0;
}

ll query (int u, int L, int R, int l, int r) {
    if (InRange (L, R, l, r)) return w[u];
    pushdown (u, L, R);
    int mid = (L + R) / 2;
    ll ans = -inf;
    if (l <= mid) ans = max (ans, query (u * 2, L, mid, l, r));
    if (r > mid) ans = max (ans, query (u * 2 + 1, mid + 1, R, l, r));
    return ans;
}

void update (int u, int L, int R, int l, int r, ll x, int type) {
    pushdown (u, L, R);
    if (InRange (L, R, l, r)) {
        maketag (u, x, type);
        return ;
    }
    int mid = (L + R) / 2;
    if (l <= mid) update (u * 2, L, mid, l, r, x, type);
    if (r > mid) update (u * 2 + 1, mid + 1, R, l, r, x, type);
    pushup (u);
}

int main () {

    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) scanf ("%lld", &a[i]);
    build (1, 1, n);
    for (int i = 1; i <= m; i ++) {
        scanf ("%d", &op);
        if (op == 1) {
            scanf ("%d%d%lld", &x, &y, &k);
            update (1, 1, n, x, y, k, 2);
        } else if (op == 2) {
            scanf ("%d%d%lld", &x, &y, &k);
            update (1, 1, n, x, y, k, 1);
        } else if (op == 3) {
            scanf ("%d%d", &x, &y);
            printf ("%lld\n", query (1, 1, n, x, y));
        }
    }

    return 0;

}