P1253 50pts求助，悬关

int4399 @ 2024-07-29 19:53:32

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,a[N];
struct tree{
    int l,r;
    long long maxx,lazy,fugai=-1e18;
}tr[N<<2];
void pushup(int u){
    tr[u].maxx=max(tr[u<<1].maxx,tr[u<<1|1].maxx);
}
void fall(int u,long long v){
    tr[u].maxx=v;
    tr[u].lazy=0;
    tr[u].fugai=v;
}
void fal(int u,long long v){
    tr[u].maxx+=v;
    tr[u].lazy+=v;
}
void pushdown(int u){
    if(tr[u].fugai!=-1e18){
        fall(u<<1,tr[u].fugai);fall(u<<1|1,tr[u].fugai);
        tr[u].fugai=-1e18;
    }
    if(tr[u].lazy!=0){
        fal(u<<1,tr[u].lazy);fal(u<<1|1,tr[u].lazy);
        tr[u].lazy=0;
    }
}
void build(int u,int l,int r){
    tr[u].l=l,tr[u].r=r;
    if(l==r){
        tr[u].maxx=a[l];
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
long long check(int u,int l,int r){
    if(l<=tr[u].l&&tr[u].r<=r) return tr[u].maxx;
    long long res=-1e18,mid=tr[u].l+tr[u].r>>1;
    pushdown(u);
    if(l<=mid) res=max(res,check(u<<1,l,r));
    if(mid<r) res=max(res,check(u<<1|1,l,r));
    return res;
}
void change(int u,int l,int r,long long x){
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].fugai=x;
        tr[u].maxx=x;
        tr[u].lazy=0;
        return;
    }
    int mid=tr[u].l+tr[u].r>>1;
    pushdown(u);
    if(l<=mid) change(u<<1,l,r,x);
    if(mid<r) change(u<<1|1,l,r,x);
    pushup(u);
}
void add(int u,int l,int r,long long x){
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].lazy+=x;
        tr[u].maxx+=x;
        return;
    }
    int mid=tr[u].l+tr[u].r>>1;
    pushdown(u);
    if(l<=mid) add(u<<1,l,r,x);
    if(mid<r) add(u<<1|1,l,r,x);
    pushup(u);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    int op,l,r;
    long long x;
    for(int i=1;i<=m;i++){
        cin>>op>>l>>r;
        if(op==3) cout<<check(1,l,r)<<endl;
        else
            cin>>x;
            if(op==1) change(1,l,r,x);
            else add(1,l,r,x);
        }
    }
    return 0;
}

by ___Furina___ @ 2024-07-29 19:58:20

@int4399 是否粘贴错了代码，只有20pts

by 5t0_0r2 @ 2024-07-29 19:59:29

@int4399 加的时候要判断如果区间推平的标记不为空（INF）时只更新区间推平标记

by ___Furina___ @ 2024-07-29 20:00:31

@int4399 你的主函数大括号全乱了……

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,a[N];
struct tree{
    int l,r;
    long long maxx,lazy,fugai=-1e18;
}tr[N<<2];
void pushup(int u){
    tr[u].maxx=max(tr[u<<1].maxx,tr[u<<1|1].maxx);
}
void fall(int u,long long v){
    tr[u].maxx=v;
    tr[u].lazy=0;
    tr[u].fugai=v;
}
void fal(int u,long long v){
    tr[u].maxx+=v;
    tr[u].lazy+=v;
}
void pushdown(int u){
    if(tr[u].fugai!=-1e18){
        fall(u<<1,tr[u].fugai);fall(u<<1|1,tr[u].fugai);
        tr[u].fugai=-1e18;
    }
    if(tr[u].lazy!=0){
        fal(u<<1,tr[u].lazy);fal(u<<1|1,tr[u].lazy);
        tr[u].lazy=0;
    }
}
void build(int u,int l,int r){
    tr[u].l=l,tr[u].r=r;
    if(l==r){
        tr[u].maxx=a[l];
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
long long check(int u,int l,int r){
    if(l<=tr[u].l&&tr[u].r<=r) return tr[u].maxx;
    long long res=-1e18,mid=tr[u].l+tr[u].r>>1;
    pushdown(u);
    if(l<=mid) res=max(res,check(u<<1,l,r));
    if(mid<r) res=max(res,check(u<<1|1,l,r));
    return res;
}
void change(int u,int l,int r,long long x){
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].fugai=x;
        tr[u].maxx=x;
        tr[u].lazy=0;
        return;
    }
    int mid=tr[u].l+tr[u].r>>1;
    pushdown(u);
    if(l<=mid) change(u<<1,l,r,x);
    if(mid<r) change(u<<1|1,l,r,x);
    pushup(u);
}
void add(int u,int l,int r,long long x){
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].lazy+=x;
        tr[u].maxx+=x;
        return;
    }
    int mid=tr[u].l+tr[u].r>>1;
    pushdown(u);
    if(l<=mid) add(u<<1,l,r,x);
    if(mid<r) add(u<<1|1,l,r,x);
    pushup(u);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    int op,l,r;
    long long x;
    for(int i=1;i<=m;i++){
        cin>>op>>l>>r;
        if(op==3) cout<<check(1,l,r)<<endl;
        else {//就这一处
            cin>>x;
            if(op==1) change(1,l,r,x);
            else add(1,l,r,x);
        }
    }
    return 0;
}

by ___Furina___ @ 2024-07-29 20:00:59

@5t0_0r2 不是这里的问题，就是主函数大括号出现了问题

by 5t0_0r2 @ 2024-07-29 20:02:24

@int4399 以下是 AC 代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,a[N];
struct tree{
    int l,r;
    long long maxx,lazy,fugai=-1e18;
}tr[N<<2];
void pushup(int u){
    tr[u].maxx=max(tr[u<<1].maxx,tr[u<<1|1].maxx);
}
void fall(int u,long long v){
    tr[u].maxx=v;
    tr[u].lazy=0;
    tr[u].fugai=v;
}
void fal(int u,long long v){//这里要改
    tr[u].maxx+=v;
    if(tr[u].fugai != -1e18)
        tr[u].fugai += v;
    else
        tr[u].lazy+=v;
}
void pushdown(int u){
    if(tr[u].fugai!=-1e18){
        fall(u<<1,tr[u].fugai);fall(u<<1|1,tr[u].fugai);
        tr[u].fugai=-1e18;
    }
    if(tr[u].lazy!=0){
        fal(u<<1,tr[u].lazy);fal(u<<1|1,tr[u].lazy);
        tr[u].lazy=0;
    }
}
void build(int u,int l,int r){
    tr[u].l=l,tr[u].r=r;
    if(l==r){
        tr[u].maxx=a[l];
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
long long check(int u,int l,int r){
    if(l<=tr[u].l&&tr[u].r<=r) return tr[u].maxx;
    long long res=-1e18,mid=tr[u].l+tr[u].r>>1;
    pushdown(u);
    if(l<=mid) res=max(res,check(u<<1,l,r));
    if(mid<r) res=max(res,check(u<<1|1,l,r));
    return res;
}
void change(int u,int l,int r,long long x){
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].fugai=x;
        tr[u].maxx=x;
        tr[u].lazy=0;
        return;
    }
    int mid=tr[u].l+tr[u].r>>1;
    pushdown(u);
    if(l<=mid) change(u<<1,l,r,x);
    if(mid<r) change(u<<1|1,l,r,x);
    pushup(u);
}
void add(int u,int l,int r,long long x){
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].lazy+=x;
        tr[u].maxx+=x;
        return;
    }
    int mid=tr[u].l+tr[u].r>>1;
    pushdown(u);
    if(l<=mid) add(u<<1,l,r,x);
    if(mid<r) add(u<<1|1,l,r,x);
    pushup(u);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    int op,l,r;
    long long x;
    for(int i=1;i<=m;i++){
        cin>>op>>l>>r;
        if(op==3) cout<<check(1,l,r)<<endl;
        else{
            cin>>x;
            if(op==1) change(1,l,r,x);
            else add(1,l,r,x);
        }
    }
    return 0;
}

by 5t0_0r2 @ 2024-07-29 20:03:35

6 看来我确实看错了（wssb）

by int4399 @ 2024-07-29 20:04:14

感谢两位大佬的建议，已关。