萌新袜子求调线段树裸题

RT，悬赏2关注

#include <bits/stdc++.h>
#define int long long
#define R register 
using namespace std;
const int N=1e6+5;
const int INF=1e18;
struct node{
    int l,r;
    int val;
    int tag_add,tag_cover;
}tr[N*10]; 
int a[N];

inline void cover_down(int p){
    int ls=p*2;
    int rs=p*2+1;
    if(tr[p].tag_cover==INF) return;
    tr[ls].val=tr[ls].tag_cover=tr[p].tag_cover;
    tr[ls].tag_add=0;
    tr[rs].val=tr[rs].tag_cover=tr[p].tag_cover;
    tr[rs].tag_add=0;
    tr[p].tag_cover=INF;
    return;
}

inline void add_down(int p){
    int ls=p*2;
    int rs=p*2+1;
    if(tr[p].tag_add==0) return;
//  cover_down(p);
    tr[ls].val+=tr[p].tag_add;
    tr[ls].tag_add+=tr[p].tag_add;
    tr[rs].val+=tr[p].tag_add;
    tr[rs].tag_add+=tr[p].tag_add;
    tr[p].tag_add=0;
    return;
}

inline void push_up(int p){
    int ls=p*2;
    int rs=p*2+1;
    tr[p].val=max(tr[ls].val,tr[rs].val);
    return;
}

inline void build(int p,int l,int r){
    tr[p].l=l;
    tr[p].r=r;
    if(l==r){
        tr[p].val=a[l];
        tr[p].tag_cover=INF;
        tr[p].tag_add=0;
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    push_up(p);
    return;
}

inline void upd_add(int p,int ql,int qr,int v){

    int l=tr[p].l;
    int r=tr[p].r;
//  cout<<"add: "<<l<<' '<<r<<' '<<v<<endl;
    int ls=p*2;
    int rs=p*2+1;
    if(ql<=l && r<=qr){
//      cout<<"find! "<<l<<' '<<r<<endl;
        cover_down(p);
        tr[p].tag_add+=v;
        tr[p].val+=v;
        return;
    }
    int mid=(l+r)/2;
    cover_down(p);
    add_down(p);

    if(ql<=mid){
        upd_add(ls,ql,qr,v);
    }
    if(mid+1<=qr){
        upd_add(rs,ql,qr,v);
    }
    push_up(p);
    return;
}

inline void upd_cover(int p,int ql,int qr,int v){
    int l=tr[p].l;
    int r=tr[p].r;
//  cout<<"cover: "<<l<<' '<<r<<' '<<v<<endl;
    int ls=p*2;
    int rs=p*2+1;
    if(ql<=l && r<=qr){
//      cout<<"find! "<<l<<' '<<r<<endl;
        tr[p].tag_cover=v;
        tr[p].val=v;
        tr[p].tag_add=0;
        return;
    }
    int mid=(l+r)/2;
    cover_down(p);
    add_down(p);

    if(ql<=mid){
        upd_cover(ls,ql,qr,v);
    }
    if(mid+1<=qr){
        upd_cover(rs,ql,qr,v);
    }
    push_up(p);
    return;
}

inline int query(int p,int ql,int qr){
    int l=tr[p].l;
    int r=tr[p].r;
    int ls=p*2;
    int rs=p*2+1;
    if(ql<=l && r<=qr){
        return tr[p].val;
    }
    cover_down(p);
    add_down(p);
    int mid=(l+r)/2;
    int res=-INF;
    if(ql<=mid){
        res=max(res,query(ls,ql,qr));
    }
    if(mid+1<=r){
        res=max(res,query(rs,ql,qr));
    }
    return res;
}
int n,q;
signed main() {
//  freopen("P1253_5.in","r",stdin);
//  freopen("P1253_5.out","w",stdout);
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    for(R int i=1;i<=n*4;i++){
        tr[i].tag_cover=INF;
    }

    for(R int i=1;i<=q;i++){
        int opt,l,r,x;
        scanf("%lld",&opt);
        if(opt==1){
            scanf("%lld%lld%lld",&l,&r,&x);
            upd_cover(1,l,r,x);
        }
        else if(opt==2){
            scanf("%lld%lld%lld",&l,&r,&x);
            upd_add(1,l,r,x);
        }
        else{
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",query(1,l,r));
        }
    }

    return 0;
}

感觉复杂度是对的啊……

这就是大常数选手吗……