玄关,10pts求助

P1253 扶苏的问题

wyf_ @ 2023-11-10 21:55:08

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
struct node{
    int l,r,v,laz1,laz2,sum,mx;
}a[4*maxn];
int n,q,b[maxn];
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=(x<<1)+(x<<3)+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
void t_build(int l,int r,int v)
{
    a[v].l=l;
    a[v].r=r;
    a[v].laz1=0;
    a[v].laz2=0;
    if(l==r)
    {
        a[v].mx=b[l];
        return ;
    }
    int mid=(l+r)>>1;
    t_build(l,mid,v<<1);
    t_build(mid+1,r,(v<<1)|1);
    a[v].mx=max(a[v<<1].mx,a[(v<<1)|1].mx);
    return ; 
}
void update(int x,int y,int v,int k,bool flag)
{
    if(!flag)
    {
        if(a[v].l>=x&&a[v].r<=y)
        {
            a[v].laz1=k;
            a[v].laz2=0;
            a[v].mx=k;
            return ;
        }
        if(a[v].laz1)
        {
            a[v<<1].laz1=a[v].laz1;
            a[v<<1].laz2=0;
            a[(v<<1)|1].laz1=a[v].laz1;
            a[(v<<1)|1].laz2=0;
            a[v].laz1=0;
            a[v].laz2=0;
        }
        int mid=(a[v].r+a[v].l)>>1;
        if(y<=mid) update(x,y,v<<1,k,0);
        else if(x>mid) update(x,y,(v<<1)|1,k,0);
        else{
            update(x,mid,v<<1,k,0);
            update(mid+1,y,(v<<1)|1,k,0);
        }
    }//修改 

    else if(flag)
    {
        if(a[v].l>=x&&a[v].r<=y)
        {
            a[v].laz1=0;
            a[v].laz2+=k;
            a[v].mx=a[v].mx+k;
            return ;
        }
        if(a[v].laz2)
        {
            a[v<<1].laz2+=a[v].laz2;
            a[v<<1].laz1=0;
            a[(v<<1)|1].laz2+=a[v].laz2;
            a[(v<<1)|1].laz1=0;
            a[v].laz2=0;
            a[v].laz1=0;
        }
        int mid=(a[v].r+a[v].l)>>1;
        if(y<=mid) update(x,y,v<<1,k,1);
        else if(x>mid) update(x,y,(v<<1)|1,k,1);
        else{
            update(x,mid,v<<1,k,1);
            update(mid+1,y,(v<<1)|1,k,1);
        }
    }//加数 
    a[v].mx=max(a[v<<1].mx,a[(v<<1)|1].mx);
    return ;
}
int t_find(int x,int y,int v)
{
    if(a[v].l>=x&&a[v].r<=y)
    {
        if(a[v].laz1) return a[v].laz1;
        else if(a[v].laz2) return a[v].laz2+a[v].mx;
        else return a[v].mx;
    } 
    if(a[v].laz1)
    {
            a[v<<1].laz1=a[v].laz1;
            a[v<<1].laz2=0;
            a[(v<<1)|1].laz1=a[v].laz1;
            a[(v<<1)|1].laz2=0;
            a[v].laz1=0;
            a[v].laz2=0;
    }
    else if(a[v].laz2)
    {
        a[v<<1].laz2+=a[v].laz2;
        a[v<<1].laz1=0;
        a[(v<<1)|1].laz2+=a[v].laz2;
        a[(v<<1)|1].laz1=0;
        a[v].laz2=0;
        a[v].laz1=0;

    }
    int mid=(a[v].l+a[v].r)>>1;
    if(y<=mid) return t_find(x,y,v<<1);
        else if(x>mid) return t_find(x,y,(v<<1)|1);
        else{
            return max(t_find(x,mid,v<<1),t_find(mid+1,y,(v<<1)|1));
        }

}
int main()
{
    n=read();
    q=read();
    for(int i=1;i<=n;i++) b[i]=read();
    t_build(1,n,1);
    while(q--)
    {
        int op,x,y,k;
        op=read();
        if(op==1)
        {
            x=read(),y=read(),k=read();
            update(x,y,1,k,0);
        }
        else if(op==2)
        {
            x=read(),y=read(),k=read();
            update(x,y,1,k,1);
        }
        else {
            x=read(),y=read();
            cout<<t_find(x,y,1)<<endl;
        }
    }
    return 0;
}

只过了#1,玄关


by tjr0513 @ 2023-11-10 21:59:42

修改操作每次两个懒标记都要下传


by 西湖水妖 @ 2023-11-11 10:11:08

《玄关》。


|