萌新求调线段树裸题

dk_qwq @ 2022-08-04 19:21:09

by 2018heyuyang @ 2022-08-04 22:31:50

没看见你的提交啊

by 2018heyuyang @ 2022-08-04 22:37:50

@dkqwq

#include<iostream>
#include<cstdio>
#define nul -1000000000000000000ll
using namespace std;
typedef long long ll;
const int N=1e6+5;
ll a[N];
struct tree{
    int l,r;
    ll maxx;
    ll add,change_to;
}t[N<<2];
void pushup(int o){t[o].maxx=max(t[o<<1].maxx,t[o<<1|1].maxx);}
void build(int o,int l,int r){
    t[o].l=l,t[o].r=r,t[o].change_to=nul;
    if(l==r){
        t[o].maxx=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    pushup(o);
}
void pushdown_add(int o){
    if(t[o].add){
        t[o<<1].maxx+=t[o].add;
        if(t[o<<1].change_to!=nul) t[o<<1].change_to+=t[o].add;
        else t[o<<1].add+=t[o].add;
        t[o<<1|1].maxx+=t[o].add;
        if(t[o<<1|1].change_to!=nul) t[o<<1|1].change_to+=t[o].add;
        else t[o<<1|1].add+=t[o].add;
        t[o].add=0;
    }
}
void pushdown_change(int o){
    if(t[o].change_to!=nul){
        t[o<<1].maxx=t[o].change_to;
        t[o<<1].change_to=t[o].change_to;
        t[o<<1].add=0;
        t[o<<1|1].maxx=t[o].change_to;
        t[o<<1|1].change_to=t[o].change_to;
        t[o<<1|1].add=0;
        t[o].change_to=nul;
    }
}
void pushdown(int o){
    pushdown_change(o),pushdown_add(o);
}
void change(int o,int ql,int qr,ll x){
    if(ql<=t[o].l&&t[o].r<=qr){
        t[o].maxx=x;
        t[o].change_to=x;
        t[o].add=0;
        return ;
    }
    pushdown(o);
    int mid=(t[o].l+t[o].r)>>1;
    if(ql<=mid) change(o<<1,ql,qr,x);
    if(mid<qr) change(o<<1|1,ql,qr,x);
    pushup(o);
}
void add(int o,int ql,int qr,ll x){
    if(ql<=t[o].l&&t[o].r<=qr){
        t[o].maxx+=x;
        if(t[o].change_to!=nul) t[o].change_to+=x,t[o].add=0;
        else t[o].add+=x;
        return ;
    }
    pushdown(o);
    int mid=(t[o].l+t[o].r)>>1;
    if(ql<=mid) add(o<<1,ql,qr,x);
    if(mid<qr) add(o<<1|1,ql,qr,x);
    pushup(o);
}
ll ask(int o,int ql,int qr){
    if(ql<=t[o].l&&t[o].r<=qr) return t[o].maxx;
    pushdown(o);
    int mid=(t[o].l+t[o].r)>>1;
    ll ans=nul;
    if(ql<=mid) ans=max(ans,ask(o<<1,ql,qr));
    if(mid<qr) ans=max(ans,ask(o<<1|1,ql,qr));
    return ans;
}
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--){
        int op;
        int l,r;
        ll x;
        scanf("%d%d%d",&op,&l,&r);
        if(op==1){
            scanf("%lld",&x);
            change(1,l,r,x);
        }
        if(op==2){
            scanf("%lld",&x);
            add(1,l,r,x);
        }
        if(op==3){
            printf("%lld\n",ask(1,l,r));
        }
    }
}

by dk_qwq @ 2022-08-05 00:19:39

@2018heyuyang 之前在本地测的，结果我忘了把pushdown_add里的t[o<<1].add+=t[o].add删了，现在AC了，谢谢大佬，打扰了