50pts，6-10悬关

dpACerFXing @ 2024-04-13 11:06:48

# include<iostream>
# include<algorithm>
# include<cmath>
# define int long long
# define endl "\n"
using namespace std;
const int maxn=1e6+1, INF=2147483647;
int n, m, a[maxn];
struct Node{
    int l, r, mmax;
    int add, change;
}tree[maxn*4];
void build_tree(int i, int l, int r) {
    tree[i].l=l; tree[i].r=r; tree[i].mmax=-INF; tree[i].change=INF;
    if(l==r) {
        tree[i].mmax=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build_tree(2*i, l, mid);
    build_tree(2*i+1, mid+1, r);
    tree[i].mmax=max(tree[2*i].mmax, tree[2*i+1].mmax);
} 
void push_down(int i) {
    if(tree[i].change!=INF) {
        tree[i*2].mmax=tree[i*2+1].mmax=tree[i].change+tree[i].add;
        tree[i*2].change=tree[i*2+1].change=tree[i].change;
        tree[i*2].add=tree[i*2+1].add=0;
    } else {
        tree[i*2].mmax+=tree[i].add;
        tree[i*2+1].mmax+=tree[i].add;
        tree[i*2].add+=tree[i].add;
        tree[i*2+1].add+=tree[i].add;
    }
    tree[i].change=INF;
    tree[i].add=0;
}
void add(int i, int l, int r, int d) {
    if(tree[i].l>=l && tree[i].r<=r) {
        tree[i].mmax+=d;
        tree[i].add+=d;
        return ;
    }
    push_down(i);
    int mid=(tree[i].l+tree[i].r)/2;
    if(l<=mid) add(2*i, l, r, d);
    if(r>=mid+1) add(2*i+1, l, r, d);
    tree[i].mmax=max(tree[2*i].mmax, tree[2*i+1].mmax);
}
void change(int i, int l, int r, int d) {
    if(tree[i].l>=l && tree[i].r<=r) {
        tree[i].mmax=d;
        tree[i].add=0;
        tree[i].change=d;
        return ;
    }
    push_down(i);
    int mid=(tree[i].l+tree[i].r)/2;
    if(l<=mid) change(2*i, l, r, d);
    if(r>=mid+1) change(2*i+1, l, r, d);
    tree[i].mmax=max(tree[2*i].mmax, tree[2*i+1].mmax);
}
int query(int i, int l, int r) {
    if(tree[i].l>=l && tree[i].r<=r) return tree[i].mmax;
    push_down(i);
    int mid=(tree[i].l+tree[i].r)/2, mmax=0;
    if(l<=mid) mmax=max(mmax, query(2*i, l, r));
    if(r>=mid+1) mmax=max(mmax, query(2*i+1, l, r));
    return mmax;
} 
signed main() {
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i];
    build_tree(1, 1, n);
    while(m--) {
        int op; cin >> op;
        if(op==1) {
            int x, y, k; cin >> x >> y >> k;
            change(1, x, y, k);
        } else if(op==2) {
            int x, y, k; cin >> x >> y >> k;
            add(1, x, y, k); 
        } else {
            int x, y; cin >> x >> y;
            cout << query(1, x, y) << endl;
        }
    }
    return 0;
}

by FlyPancake @ 2024-04-13 16:09:29

@dpACerLZJun

# include<iostream>
# include<algorithm>
# include<cmath>
# define int long long
# define endl "\n"
using namespace std;
const int maxn=1e6+1, INF=2147386547;
int n, m, a[maxn];
struct Node{
    int l, r, mmax;
    int add, change;
}tree[maxn*4];
void build_tree(int i, int l, int r) {
    tree[i].l=l; tree[i].r=r; tree[i].mmax=-INF; tree[i].change=INF;
    if(l==r) {
        tree[i].mmax=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build_tree(2*i, l, mid);
    build_tree(2*i+1, mid+1, r);
    tree[i].mmax=max(tree[2*i].mmax, tree[2*i+1].mmax);
} 
void push_down(int i) {
    if(tree[i].change!=INF) {
        tree[i*2].mmax=tree[i*2+1].mmax=tree[i].change+tree[i].add;
        tree[i*2].change=tree[i*2+1].change=tree[i].change;
        tree[i*2].add=tree[i*2+1].add=tree[i].add;
    } else {
        tree[i*2].mmax+=tree[i].add;
        tree[i*2+1].mmax+=tree[i].add;
        tree[i*2].add+=tree[i].add;
        tree[i*2+1].add+=tree[i].add;
    }
    tree[i].change=INF;
    tree[i].add=0;
}
void add(int i, int l, int r, int d) {
    if(tree[i].l>=l && tree[i].r<=r) {
        tree[i].mmax+=d;
        tree[i].add+=d;
        return ;
    }
    push_down(i);
    int mid=(tree[i].l+tree[i].r)/2;
    if(l<=mid) add(2*i, l, r, d);
    if(r>=mid+1) add(2*i+1, l, r, d);
    tree[i].mmax=max(tree[2*i].mmax, tree[2*i+1].mmax);
}
void change(int i, int l, int r, int d) {
    if(tree[i].l>=l && tree[i].r<=r) {
        tree[i].mmax=d;
        tree[i].add=0;
        tree[i].change=d;
        return ;
    }
    push_down(i);
    int mid=(tree[i].l+tree[i].r)/2;
    if(l<=mid) change(2*i, l, r, d);
    if(r>=mid+1) change(2*i+1, l, r, d);
    tree[i].mmax=max(tree[2*i].mmax, tree[2*i+1].mmax);
}
int query(int i, int l, int r) {
    if(tree[i].l>=l && tree[i].r<=r) return tree[i].mmax;
    push_down(i);
    int mid=(tree[i].l+tree[i].r)/2, mmax=-1e18;
    if(l<=mid) mmax=max(mmax, query(2*i, l, r));
    if(r>=mid+1) mmax=max(mmax, query(2*i+1, l, r));
    return mmax;
} 
signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i];
    build_tree(1, 1, n);
    while(m--) {
        int op; cin >> op;
        if(op==1) {
            int x, y, k; cin >> x >> y >> k;
            change(1, x, y, k);
        } else if(op==2) {
            int x, y, k; cin >> x >> y >> k;
            add(1, x, y, k); 
        } else {
            int x, y; cin >> x >> y;
            cout << query(1, x, y) << endl;
        }
    }
    return 0;
}

问题1：第28行应赋值为 tree[x].add

问题2：第66行 mmax 的值应该更小，因为答案可能是负数

问题3：请使用较快的输入输出方式

\\\改了之后应该能过

by jmjy1928 @ 2024-04-13 21:21:52

6

by dpACerFXing @ 2024-04-14 08:52:32

@FlyPancake 谢谢大佬 已AC

by dpACerFXing @ 2024-04-14 08:54:49

给了4个关注