50分 6-9WA 10RE

emo_male_god @ 2023-10-20 00:14:27

#include <iostream>
#define int long long

#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)

using namespace std;

const int N = 1e6 + 5;

int t1[N << 2], t2[N << 2];
int t[N << 2], inf = 1145148100;
int n, m;

void cover(int p, int l, int r, int k)
{
    if (k == -inf) return;
    t1[p] = 0;
    t2[p] = t[p] = k;
}

void add(int p, int l, int r, int k)
{
    if (k == 0) return;

    int mid = (l + r) >> 1;
    cover(ls(p), l, mid + 1, t2[p]);
    cover(rs(p), mid + 1, r, t2[p]);
    t1[p] += k;
    t[p] += k;
}

void push_down(int p, int l, int r)
{
    int mid = (l + r) >> 1;
    cover(ls(p), l, mid, t2[p]);
    cover(rs(p), mid + 1, r, t2[p]);
    add(ls(p), l, mid, t1[p]);
    add(rs(p), mid + 1, r, t1[p]);
    t2[p] = -inf, t1[p] = 0;
}

void build(int p, int l, int r)
{
    if (l == r)
    {
        scanf("%lld", &t[p]);
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    t[p] = max(t[ls(p)], t[rs(p)]); // push_up
}

void update(int x, int y, int op, int k, int p, int l, int r)
{
    if (x <= l && r <= y)
    {
        if (op == 1) cover(p, l, r, k); // op == 1 是覆盖！
        if (op == 2) add(p, l, r, k); // op == 2 是加法！
        return;
    }
    push_down(p, l, r);
    int mid = (l + r) >> 1;
    if (x <= mid) update(x, y, op, k, ls(p), l, mid);
    if (y >  mid) update(x, y, op, k, rs(p), mid + 1, r);
    t[p] = max(t[ls(p)], t[rs(p)]); // push_up
}

int query(int x, int y, int p, int l, int r)
{
    if (x <= l && r <= y) return t[p];
    push_down(p, l, r);
    int res = -inf;
    int mid = (l + r) >> 1;
    if (x <= mid) res = max(res, query(x, y, ls(p), l, mid));
    if (y >  mid) res = max(res, query(x, y, rs(p), mid + 1, r));
    return res;
}

signed main()
{
    scanf("%lld%lld", &n, &m);
    build(1, 1, n);
    for (int i = 1; i <= n * 4; i ++ ) t2[i] = -inf;
    int op, x, y, k;
    while (m -- )
    {
        scanf("%lld%lld%lld", &op, &x, &y);
        if (op <= 2) scanf("%lld", &k), update(x, y, op, k, 1, 1, n);
        else printf("%lld\n", query(x, y, 1, 1, n));
    }
    return 0;
}

by jr_zch @ 2023-10-20 08:19:22

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn=1e6+7,inf=1e18;
int n,m,op,u,v,x;
int a[maxn],jntm[maxn<<2],lazya[maxn<<2],lazym[maxn<<2];

void pushdown(int rt){
    if(lazym[rt]){
        jntm[rt<<1]+=lazym[rt];
        jntm[rt<<1|1]+=lazym[rt];
        if(lazya[rt<<1]!=inf) lazya[rt<<1]+=lazym[rt];
        else lazym[rt<<1]+=lazym[rt];
        if(lazya[rt<<1|1]!=inf) lazya[rt<<1|1]+=lazym[rt];
        else lazym[rt<<1|1]+=lazym[rt];
        lazym[rt]=0;
    }
    if(lazya[rt]!=inf){
        jntm[rt<<1]=lazya[rt];
        jntm[rt<<1|1]=lazya[rt];
        lazya[rt<<1]=lazya[rt];
        lazya[rt<<1|1]=lazya[rt];
        lazym[rt<<1]=lazym[rt<<1|1]=0;
        lazya[rt]=inf;
    }
    return ;
}

void build(int rt,int l,int r){
    if(l==r){
        jntm[rt]=a[l];
        return ;
    }
    int mid=l+r>>1;
    build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
    jntm[rt]=max(jntm[rt<<1],jntm[rt<<1|1]);
    return ;
}

void update(int rt,int l,int r,int x,int y,int op,int val){
    if(x<=l&&y>=r){
        if(op==1) jntm[rt]=val,lazym[rt]=0,lazya[rt]=val;
        if(op==2&&lazya[rt]!=inf) jntm[rt]+=val,lazya[rt]+=val;
        if(op==2&&lazya[rt]==inf) jntm[rt]+=val,lazym[rt]+=val;
        return ;
    }
    pushdown(rt);
    int mid=l+r>>1;
    if(x<=mid) update(rt<<1,l,mid,x,y,op,val);
    if(y>mid) update(rt<<1|1,mid+1,r,x,y,op,val);
    jntm[rt]=max(jntm[rt<<1],jntm[rt<<1|1]); 
    return ;
}

int query(int rt,int l,int r,int x,int y){
    if(x<=l&&y>=r) return jntm[rt];
    pushdown(rt);
    int mid=l+r>>1,res=-inf;
    if(x<=mid) res=max(res,query(rt<<1,l,mid,x,y));
    if(y>mid) res=max(res,query(rt<<1|1,mid+1,r,x,y));
    return res;
}

signed main(){
//  freopen("6.in","r",stdin);
//  freopen("ans.txt","w",stdout);
    scanf("%lld%lld",&n,&m);
    for(int i=0;i<n<<2;i++) lazya[i]=inf;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%lld",&op,&u,&v);
        if(op==1) scanf("%lld",&x),update(1,1,n,u,v,op,x);
        else if(op==2) scanf("%lld",&x),update(1,1,n,u,v,op,x);
        else printf("%lld\n",query(1,1,n,u,v));
    }
    return 0;
}