20pts球著

Z1qqurat @ 2023-01-01 18:58:36

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, inf = 1145141919810;
int n, q, tree[N << 2], tag[N << 2], tag2[4 * N], a[N];

void init() { for (int i = 0; i < (N << 2); ++i) tag[i] = tag2[i] = inf; }

void pushup(int cur) { tree[cur] = max(tree[cur << 1], tree[cur << 1 | 1]); }

void build(int cur, int lt, int rt) {
    if(lt == rt) {
        tree[cur] = a[lt];
        return ;
    }
    int mid = (lt + rt) >> 1;
    build(cur << 1, lt, mid);
    build(cur << 1 | 1, mid + 1, rt);
    return pushup(cur);
}

void addtag(int cur, int lt, int rt, int val) { 
    //if(val == inf) return ;
    tag[cur] += val, tree[cur] += val; 
}

void addtag2(int cur, int lt, int rt, int val) { 
    //if(val == inf) return ;
    tag2[cur] = val, tag[cur] = inf, tree[cur] = val; 
}

void pushdown(int cur, int lt, int rt) {
    if(tag[cur] != inf) {
        int mid = (lt + rt) >> 1;
        addtag(cur << 1, lt, mid, tag[cur]);
        addtag(cur << 1 | 1, mid + 1, rt, tag[cur]);
    }
    tag[cur] = inf;
}

void pushdown2(int cur, int lt, int rt) {
    if(tag2[cur] != inf) {
        int mid = (lt + rt) >> 1;
        addtag2(cur << 1, lt, mid, tag2[cur]);
        addtag2(cur << 1 | 1, mid + 1, rt, tag2[cur]);
    }
    tag2[cur] = inf;
}

int query(int cur, int lt, int rt, int qx, int qy) {
    if(qx > rt || qy < lt) return -inf;
    if(qx <= lt && rt <= qy) return tree[cur];
    pushdown2(cur, lt, rt);
    pushdown(cur, lt, rt);
    int mid = (lt + rt) >> 1;
    return max(query(cur << 1, lt, mid, qx, qy), query(cur << 1 | 1, mid + 1, rt, qx, qy));
}

void modify(int cur, int lt, int rt, int qx, int qy, int val) {
    if(qx > rt || qy < lt) return ;
    if(qx <= lt && rt <= qy) return addtag(cur, lt, rt, val);
    pushdown2(cur, lt, rt);
    pushdown(cur, lt, rt);
    int mid = (lt + rt) >> 1;
    modify(cur << 1, lt, mid, qx, qy, val);
    modify(cur << 1 | 1, mid + 1, rt, qx, qy, val);
    return pushup(cur);
}

void modify2(int cur, int lt, int rt, int qx, int qy, int val) {
    if(qx > rt || qy < lt) return ;
    if(qx <= lt && rt <= qy) return addtag2(cur, lt, rt, val);
    pushdown2(cur, lt, rt);
    pushdown(cur, lt, rt);
    int mid = (lt + rt) >> 1;
    modify2(cur << 1, lt, mid, qx, qy, val);
    modify2(cur << 1 | 1, mid + 1, rt, qx, qy, val);
    return pushup(cur);
}

signed main() {
    scanf("%lld%lld", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    init();
    build(1, 1, n);
    for (int i = 1; i <= q; ++i) {
        int op, l, r, x;
        scanf("%lld%lld%lld", &op, &l, &r);
        if(op == 1) {
            scanf("%lld", &x);
            modify2(1, 1, n, l, r, x);
        }
        if(op == 2) {
            scanf("%lld", &x);
            modify(1, 1, n, l, r, x);
        }
        if(op == 3) {
            printf("%lld\n", query(1, 1, n, l, r));
        }
    }
    return 0;
}

by ByGones @ 2023-01-01 19:19:26

@Ziqqurat

void addtag(int cur, int lt, int rt, int val) {
    if(tag[cur]==inf)tag[cur]=0;
    tag[cur] += val, tree[cur] += val;
}

by raincity @ 2023-01-01 20:12:27

@Ziqqurat 如果说代码的意思是 tag 为区间加标记，为 inf 时为空，那区间加的时候要把 inf 变成 0 的吧。

by raincity @ 2023-01-01 20:13:25

指 addtag 里面。所以为什么不把 0 当作没有区间加标记。

by Z1qqurat @ 2023-01-01 22:42:11

@ByGones @ClHg2 您好，我发现我贴错了一个代码，怎么办？？？

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, inf = 1145141919810;
int n, q, tree[N << 2], tag[N << 2], tag2[4 * N], a[N];

void init() { for (int i = 0; i < (N << 2); ++i) tag[i] = tag2[i] = inf; }

void pushup(int cur) { tree[cur] = max(tree[cur << 1], tree[cur << 1 | 1]); }

void build(int cur, int lt, int rt) {
    if(lt == rt) {
        tree[cur] = a[lt];
        return ;
    }
    int mid = (lt + rt) >> 1;
    build(cur << 1, lt, mid);
    build(cur << 1 | 1, mid + 1, rt);
    return pushup(cur);
}

void addtag(int cur, int lt, int rt, int val) { 
    //if(val == inf) return ;
    tag[cur] += val, tree[cur] += val; 
}

void addtag2(int cur, int lt, int rt, int val) { 
    //if(val == inf) return ;
    tag2[cur] = val, tag[cur] = inf, tree[cur] = val; 
}

void pushdown(int cur, int lt, int rt) {
    if(tag[cur] != inf) {
        int mid = (lt + rt) >> 1;
        addtag(cur << 1, lt, mid, tag[cur]);
        addtag(cur << 1 | 1, mid + 1, rt, tag[cur]);
    }
    tag[cur] = inf;
}

void pushdown2(int cur, int lt, int rt) {
    if(tag2[cur] != inf) {
        int mid = (lt + rt) >> 1;
        addtag2(cur << 1, lt, mid, tag2[cur]);
        addtag2(cur << 1 | 1, mid + 1, rt, tag2[cur]);
    }
    tag2[cur] = inf;
}

int query(int cur, int lt, int rt, int qx, int qy) {
    if(qx > rt || qy < lt) return -inf;
    if(qx <= lt && rt <= qy) return tree[cur];
    pushdown2(cur, lt, rt);
    pushdown(cur, lt, rt);
    int mid = (lt + rt) >> 1;
    return max(query(cur << 1, lt, mid, qx, qy), query(cur << 1 | 1, mid + 1, rt, qx, qy));
}

void modify(int cur, int lt, int rt, int qx, int qy, int val) {
    if(qx > rt || qy < lt) return ;
    if(qx <= lt && rt <= qy) return addtag(cur, lt, rt, val);
    pushdown2(cur, lt, rt);
    pushdown(cur, lt, rt);
    int mid = (lt + rt) >> 1;
    modify(cur << 1, lt, mid, qx, qy, val);
    modify(cur << 1 | 1, mid + 1, rt, qx, qy, val);
    return pushup(cur);
}

void modify2(int cur, int lt, int rt, int qx, int qy, int val) {
    if(qx > rt || qy < lt) return ;
    if(qx <= lt && rt <= qy) return addtag2(cur, lt, rt, val);
    pushdown2(cur, lt, rt);
    pushdown(cur, lt, rt);
    int mid = (lt + rt) >> 1;
    modify2(cur << 1, lt, mid, qx, qy, val);
    modify2(cur << 1 | 1, mid + 1, rt, qx, qy, val);
    return pushup(cur);
}

signed main() {
    scanf("%lld%lld", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    init();
    build(1, 1, n);
    for (int i = 1; i <= q; ++i) {
        int op, l, r, x;
        scanf("%lld%lld%lld", &op, &l, &r);
        if(op == 1) {
            scanf("%lld", &x);
            modify2(1, 1, n, l, r, x);
        }
        if(op == 2) {
            scanf("%lld", &x);
            modify(1, 1, n, l, r, x);
        }
        if(op == 3) {
            printf("%lld\n", query(1, 1, n, l, r));
        }
    }
    return 0;
}

by ByGones @ 2023-01-01 23:15:48

@Ziqqurat 两个代码不一样嘛，反正问题一样）

by Z1qqurat @ 2023-01-02 10:11:17

@ClHg2 @ByGones 谢谢奆佬，已经解决力qwq