20pts,急

P1253 扶苏的问题

Oier_szc @ 2022-11-24 21:45:49

#include <bits/stdc++.h>
#define int long long
using namespace std;
const long long NF=1145141919810;
int n,q,a[1000005],tree[4*1000005],tag1[4*1000005],tag2[4*1000005];
int read()
{
    register char c;
    register int x=0,f=1;
    c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c-'0');
        c=getchar();
    }
    return x*f;
}
void fa_change(int u)
{
    tree[u]=max(tree[u*2],tree[u*2+1]);
}
void add1(int u,int x)
{
    tree[u]=x;
    tag1[u]=x;
    tag2[u]=0;
}
void add2(int u,int x)
{
    tree[u]+=x;
    if(tag1[u]!=NF) tag1[u]+=x;
    else tag2[u]+=x;
}
void pushdown1(int u)
{
    if(tag1[u]!=NF)
    {
        add1(u*2,tag1[u]);add1(u*2+1,tag1[u]);
        tag1[u]=NF;
    }
    else if(tag2[u]!=0)
    {
        add2(u*2,tag2[u]);add2(u*2+1,tag2[u]);
        tag2[u]=0;
    }

}
void creattree(int u,int l,int r)
{
    if(l==r)
    {
        tree[u]=a[l];
        return;
    }
    int mid=l+r>>1;
    creattree(u*2,l,mid);
    creattree(u*2+1,mid+1,r);
    fa_change(u);
}
void update1(int u,int l,int r,int L,int R,int x)
{
    if(L<=l&&r<=R)
    {
        add1(u,x);
        return;
    }
    pushdown1(u);
    int mid=l+r>>1;
    if(L<=mid) update1(u*2,l,mid,L,R,x);
    if(R>mid) update1(u*2+1,mid+1,r,L,R,x);
    fa_change(u);
}
void update2(int u,int l,int r,int L,int R,int x)
{
    if(L<=l&&r<=R)
    {
        add2(u,x);
        return;
    }
    pushdown1(u);
    int mid=l+r>>1;
    if(L<=mid) update2(u*2,l,mid,L,R,x);
    if(R>mid) update2(u*2+1,mid+1,r,L,R,x);
    fa_change(u);
}
int query(int u,int l,int r,int L,int R)
{
    if(L<=l&&r<=R) return tree[u];
    pushdown1(u);
    int mid=l+r>>1,res=-9e18;
    if(L<=mid) res=max(res,query(u*2,l,mid,L,R));
    if(R>mid) res=max(res,query(u*2+1,mid+1,r,L,R));
    return res;
}
signed main()
{
    //cout<<-2e18<<endl;
    n=read();q=read();
    //printf("%d%d",n,q);
    for(int i=1;i<=n;++i) 
    {
        a[i]=read();
        //printf("%d",a[i]);
    }
    creattree(1,1,n);
    //for(int i=1;i<=20;++i) printf("%d:%d\n",i,tree[i]);
    while(q--)
    {
        //printf("%lld\n",tree[12]);
        int op,l,r,x;
        op=read();
        if(op==1)
        {
            l=read();r=read();x=read();
            update1(1,1,n,l,r,x);
        }
        if(op==2)
        {
            l=read();r=read();x=read();
            update2(1,1,n,l,r,x);
        }
        if(op==3)
        {
            l=read();r=read();
            printf("%lld\n",query(1,1,n,l,r));
        }
    }

    return 0;
}

救救孩子QAQ


by Oier_szc @ 2022-11-24 21:49:55

万一有什么低级错误dalao们别喷
萌新线段树不够熟练


by Oier_szc @ 2022-11-24 21:58:48

回答者必关注


by Oier_szc @ 2022-11-24 22:21:42

已AC,没初始化标记
算警示后人,此帖结


|