线段树求助!求助!qwq 20pts

P1253 扶苏的问题

lizichang @ 2023-02-20 22:18:03

#include<bits/stdc++.h>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=1e6+5;
ll n,q,a[N];
struct node
{
    ll maxx,l,r,col,num,p;
    node()
    {
        l=r=col=num=p=0;//p=1所有改为num,p=2所有加col
        maxx=-99999999;
    }
    void color(ll op,ll x)
    {
        if(op==1)
            maxx=x,col=0,num=x,p=1;
        else
        {
            maxx+=x;
            if(p=1)     num+=x;
            else    col+=x,p=2;
        }
    }
}t[N<<2];
void update(ll tr)
{
    t[tr].l=t[tr<<1].l;
    t[tr].r=t[tr<<1|1].r;
    t[tr].maxx=max(t[tr<<1].maxx,t[tr<<1|1].maxx);
}
void push_col(ll tr)
{
    if(!t[tr].p)    return ;
    if(t[tr].p==1)
    {
        t[tr<<1].color(1,t[tr].num);
        t[tr<<1|1].color(1,t[tr].num);
        t[tr].num=0;
        t[tr].p=0;
    }
    else
    {
        t[tr<<1].color(2,t[tr].col);
        t[tr<<1|1].color(2,t[tr].col);
        t[tr].col=0;
        t[tr].p=0;
    }
}
void build(ll tr,ll l,ll r)
{
    if(l==r)
    {
        t[tr].l=t[tr].r=l;
        t[tr].maxx=a[l];
        return ;
    }
    ll m=(l+r)>>1;
    build(tr<<1,l,m);
    build(tr<<1|1,m+1,r);
    update(tr);
}
ll query(ll tr,ll nl,ll nr)
{
    if(nl<=t[tr].l&&t[tr].r<=nr)    return t[tr].maxx;
    push_col(tr);
    ll m=(t[tr].l+t[tr].r)>>1;
    if(m>=nl)
    {
        if(m<nr)    return max(query(tr<<1,nl,nr),query(tr<<1|1,nl,nr));
        return query(tr<<1,nl,nr);
    }
    return query(tr<<1|1,nl,nr);
}
void modify(ll tr,ll nl,ll nr,ll op,ll x)
{
    if(nl<=t[tr].l&&t[tr].r<=nr)
    {
        t[tr].color(op,x);
        return ;
    }
    push_col(tr);
    ll m=(t[tr].l+t[tr].r)>>1;
    if(nl<=m)   modify(tr<<1,nl,nr,op,x);
    if(nr>m)    modify(tr<<1|1,nl,nr,op,x);
    update(tr);
}
int main()
{
    ll op,x,y,z;
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++)   scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        scanf("%lld%lld%lld",&op,&x,&y);
        if(op!=3)
        {
            scanf("%lld",&z);
            modify(1,x,y,op,z);
        }
        else
            printf("%lld\n",query(1,x,y));
    }
    return 0;
}

by Lucky_Cloud @ 2023-04-17 14:05:12

@lizichang DALAO, 我也跟你一样20分求解答,谢谢sto


|