线段树50pts 求调 谢谢

lct201714 @ 2024-07-30 22:49:29

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
template <class T>
inline void read(T &res){
    char c;bool f=0;
    while(!isdigit(c=getchar())) if(c=='-') f=1;
    res=(c^48);
    while(isdigit(c=getchar())) res=(res<<1)+(res<<3)+(c^48);
    if(f) res=~res+1;
}
int n,q,op,l,r;
long long a[N],x;
#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
struct Tree{
    long long max;
    long long tag_add,tag_rep;
}t[N*4];
void build(int u,int l,int r){
    t[u].tag_rep=LONG_LONG_MAX;
    t[u].max=LONG_LONG_MIN; 
    if(l==r) {t[u].max=a[l];return ;}
    build(ls,l,mid);
    build(rs,mid+1,r);
    t[u].max=max(t[ls].max,t[rs].max);
}
void add(int u,int l,int r,long long x){
    t[u].tag_add+=x; t[u].max+=x;
}
void replace(int u,int l,int r,long long x){
    t[u].tag_rep=x; t[u].tag_add=0; t[u].max=x;
}
void push_down(int u,int l,int r){
    if(t[u].tag_rep!=LONG_LONG_MAX){
        replace(ls,l,mid,t[u].tag_rep);
        replace(rs,mid+1,r,t[u].tag_rep);
        t[u].tag_rep=LONG_LONG_MAX;
    }
    if(t[u].tag_add){
        add(ls,l,mid,t[u].tag_add);
        add(rs,mid+1,r,t[u].tag_add);
        t[u].tag_add=0;
    }
}
long long query(int u,int l,int r,int ql,int qr){
    if(r<ql||l>qr) return 0;
    push_down(u,l,r);
    if(ql<=l&&qr>=r) return t[u].max;
    return max(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));
}
void modify(int u,int l,int r,int ql,int qr,long long x,int op){
    if(qr<l||r<ql) return ;
    if(ql<=l&&r<=qr){
        if(op==1) return replace(u,l,r,x);
        else return add(u,l,r,x);
    }
    push_down(u,l,r);
    modify(ls,l,mid,ql,qr,x,op);
    modify(rs,mid+1,r,ql,qr,x,op);
    t[u].max=max(t[ls].max,t[rs].max);
}
int main(){
    read(n);read(q);
    for(int i=1;i<=n;i++) read(a[i]);
    build(1,1,n);
    while(q--){
        read(op);read(l);read(r);
        if(op==3){
            printf("%lld\n",query(1,1,n,l,r));
        }
        else{
            read(x);
            modify(1,1,n,l,r,x,op);
        }
    }
    return 0;
}

by LiujunjiaNC @ 2024-07-31 07:31:12

@lct201714 AC了你自己看把

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
template <class T>
inline void read(T &res){
    char c;bool f=0;
    while(!isdigit(c=getchar())) if(c=='-') f=1;
    res=(c^48);
    while(isdigit(c=getchar())) res=(res<<1)+(res<<3)+(c^48);
    if(f) res=~res+1;
}
int n,q,op,l,r;
long long a[N],x;
#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
//----------------------this
#define none -1145141919180
struct Tree{
    long long max;
    long long tag_add,tag_rep;
}t[N*4];
void build(int u,int l,int r){
    //----------------------this
    t[u].tag_rep = none;
    t[u].max=LONG_LONG_MIN; 
    if(l==r) {t[u].max=a[l];return ;}
    build(ls,l,mid);
    build(rs,mid+1,r);
    t[u].max=max(t[ls].max,t[rs].max);
}
void add(int u,int l,int r,long long x){
    t[u].tag_add+=x; t[u].max+=x;
}
void replace(int u,int l,int r,long long x){
    t[u].tag_rep=x; t[u].tag_add=0; t[u].max=x;
}
void push_down(int u,int l,int r){
    if(t[u].tag_rep!=none){
        replace(ls,l,mid,t[u].tag_rep);
        replace(rs,mid+1,r,t[u].tag_rep);
        t[u].tag_rep=none;
        //----------------------this
        t[ls].tag_add = t[rs].tag_add = 0;
    }
    if(t[u].tag_add){
        add(ls,l,mid,t[u].tag_add);
        add(rs,mid+1,r,t[u].tag_add);
        t[u].tag_add=0;
    }
}
long long query(int u,int l,int r,int ql,int qr){
    //----------------------this
    if(r<ql||l>qr) return none;
    push_down(u,l,r);
    if(ql<=l&&qr>=r) return t[u].max;
    return max(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));
}
void modify(int u,int l,int r,int ql,int qr,long long x,int op){
    if(qr<l||r<ql) return;
    if(ql<=l&&r<=qr){
        if(op==1) return replace(u,l,r,x);
        else return add(u,l,r,x);
    }
    push_down(u,l,r);
    modify(ls,l,mid,ql,qr,x,op);
    modify(rs,mid+1,r,ql,qr,x,op);
    t[u].max=max(t[ls].max,t[rs].max);
}
int main(){
    read(n);read(q);
    for(int i=1;i<=n;i++) read(a[i]);
    build(1,1,n);
    while(q--){
        read(op);read(l);read(r);
        if(op==3){
            printf("%lld\n",query(1,1,n,l,r));
        }
        else{
            read(x);
            modify(1,1,n,l,r,x,op);
        }
    }
    return 0;
}

by lct201714 @ 2024-07-31 11:22:54

@LiujunjiaNC 感谢明白了