WA 7 ~ 10,求调谢谢！

Inferior_dust @ 2023-11-16 13:54:18

#include <iostream>
#include <cstdio>
using namespace std;

#define LL long long

const LL N = 1e6 + 10;
const LL INF = 9223372036854775807;

LL read() {
    LL x = 0;
    LL f = 1;
    char c = getchar();
    while(c > '9' || c < '0') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c <= '9' && c >= '0') {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return x * f;
}

void write(LL x) {
    if(x < 0) x = -x, putchar('-');
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int n, q;

LL a[N];

LL MAX[N * 4];
LL mark[N * 4];

LL f[N * 4];
LL prom[N * 4]; 

void push_down(LL t) {
    if(f[t]) {
        prom[t * 2] = prom[t];
        prom[t * 2 + 1] = prom[t];
        MAX[t * 2] = prom[t];
        MAX[t * 2 + 1] = prom[t];

        mark[t] = 0;
        mark[t * 2] = 0;
        mark[t * 2 + 1] = 0;

        prom[t] = 0;
        f[t] = false;
        f[t * 2] = true;
        f[t * 2 + 1] = true;
    }
    else {
        mark[t * 2] += mark[t];
        mark[t * 2 + 1] += mark[t];
        MAX[t * 2] += mark[t];
        MAX[t * 2 + 1] += mark[t];
        mark[t] = 0;
    }
}

void build(LL l, LL r, LL t) {
    if(l == r) MAX[t] = a[l];
    else {
        LL mid = (l + r) >> 1;
        build(l, mid, t * 2);
        build(mid + 1, r, t * 2 + 1);
        MAX[t] = max(MAX[t * 2], MAX[t * 2 + 1]);
    }
}

void update(LL L, LL R, LL l, LL r, LL t, LL val, LL op) {
    if(r < L || l > R) return ;
    else if(l >= L && r <= R) {
        if(op == 1) {
            f[t] = true;
            if(l < r) prom[t] = val;
            MAX[t] = val;
        }
        else {
            MAX[t] += val;
            if(l < r) mark[t] += val;
        }
    }
    else {
        LL mid = (l + r) >> 1;
        push_down(t);
        update(L, R, l, mid, t * 2, val, op);
        update(L, R, mid + 1, r, t * 2 + 1, val, op);
        MAX[t] = max(MAX[t * 2], MAX[t * 2 + 1]);
    }
}

LL query(LL L, LL R, LL l, LL r, LL t) {
    if(r < L || l > R) return -INF;
    else if(l >= L && r <= R) {
        return MAX[t];
    }
    else {
        LL mid = (l + r) >> 1;
        push_down(t);
        LL L_MAX = query(L, R, l, mid, t * 2);
        LL R_MAX = query(L, R, mid + 1, r, t * 2 + 1);
        return max(L_MAX, R_MAX);
    }
}

int main()
{
    n = read();
    q = read();
    for(int i = 1; i <= n; i ++) a[i] = read();

    build(1, n, 1);

    for(int i = 1; i <= q; i ++) {
        LL op, l, r, x;
        op = read();
        if(op == 1) {
            l = read();
            r = read();
            x = read();
            update(l, r, 1, n, 1, x, 1);
        }
        else if(op == 2) {
            l = read();
            r = read();
            x = read();
            update(l, r, 1, n, 1, x, 2);
        }
        else {
            l = read();
            r = read();
            write(query(l, r, 1, n, 1));
            putchar('\n');
        }
    }
    return 0;
}

by Rainylower @ 2023-11-16 14:30:18

push_down操作有点小问题，改成这样就行了。

#include <iostream>
#include <cstdio>
using namespace std;

#define LL long long
#define int long long
const LL N = 1e6 + 10;
const LL INF = 1e18;

LL read() {
    LL x = 0;
    LL f = 1;
    char c = getchar();
    while(c > '9' || c < '0') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c <= '9' && c >= '0') {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return x * f;
}

void write(LL x) {
    if(x < 0) x = -x, putchar('-');
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int n, q;

LL a[N];

LL MAX[N * 4];
LL mark[N * 4];

LL f[N * 4];
LL prom[N * 4]; 

void push_down(LL t) {
    if(f[t]) {
        prom[t * 2] = prom[t];
        prom[t * 2 + 1] = prom[t];
        MAX[t * 2] = prom[t];
        MAX[t * 2 + 1] = prom[t];
        mark[t * 2 + 1] = 0;
        mark[t * 2] = 0;
        prom[t] = 0;
        f[t] = false;
        f[t * 2] = true;
        f[t * 2 + 1] = true;
    }
    if(mark[t]){
        mark[t * 2] += mark[t];
        mark[t * 2 + 1] += mark[t];
        MAX[t * 2] += mark[t];
        MAX[t * 2 + 1] += mark[t];
        mark[t] = 0;
    }
}

void build(LL l, LL r, LL t) {
    if(l == r) MAX[t] = a[l];
    else {
        LL mid = (l + r) >> 1;
        build(l, mid, t * 2);
        build(mid + 1, r, t * 2 + 1);
        MAX[t] = max(MAX[t * 2], MAX[t * 2 + 1]);
    }
}

void update(LL L, LL R, LL l, LL r, LL t, LL val, LL op) {
    if(r < L || l > R) return ;
    else if(l >= L && r <= R) {
        if(l < r)push_down(t);
        if(op == 1) {
            f[t] = true;
            if(l < r) prom[t] = val,mark[t] = 0;
            MAX[t] = val;
        }
        else {
            MAX[t] += val;
            if(l < r) mark[t] += val;
        }
    }
    else {
        LL mid = (l + r) >> 1;
        push_down(t);
        update(L, R, l, mid, t * 2, val, op);
        update(L, R, mid + 1, r, t * 2 + 1, val, op);
        MAX[t] = max(MAX[t * 2], MAX[t * 2 + 1]);
    }
}

LL query(LL L, LL R, LL l, LL r, LL t) {
    if(r < L || l > R) return -INF;
    else if(l >= L && r <= R) {
        if(l < r)push_down(t);
        return MAX[t];
    }
    else {
        LL mid = (l + r) >> 1;
        push_down(t);
        LL L_MAX = query(L, R, l, mid, t * 2);
        LL R_MAX = query(L, R, mid + 1, r, t * 2 + 1);
        return max(L_MAX, R_MAX);
    }
}

signed main()
{
    n = read();
    q = read();
    for(int i = 1; i <= n; i ++) a[i] = read();

    build(1, n, 1);

    for(int i = 1; i <= q; i ++) {
        LL op, l, r, x;
        op = read();
        if(op == 1) {
            l = read();
            r = read();
            x = read();
            update(l, r, 1, n, 1, x, 1);
        }
        else if(op == 2) {
            l = read();
            r = read();
            x = read();
            update(l, r, 1, n, 1, x, 2);
        }
        else {
            l = read();
            r = read();
            write(query(l, r, 1, n, 1));
            putchar('\n');
        }
    }
    return 0;
}

by Inferior_dust @ 2023-11-17 15:26:01

@Rainylower 谢谢了!