求条，悬关

2012zxt @ 2024-01-30 10:19:47

by 2012zxt @ 2024-01-30 10:19:59

@woshidadanda

by 2012zxt @ 2024-01-30 10:20:20

@woshishadanda

by timmyliao @ 2024-01-30 10:31:32

AC

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N=1e6+5;
class Node{
    public:
        ll maxn,a,b;
        ll l,r;
}tree[N<<2];
ll arr[N];
void build(int index,ll l,ll r)
{
    tree[index].l=l;tree[index].r=r;
    tree[index].a=1;tree[index].b=0;
    if(l==r)
    {
        tree[index].maxn=arr[l];
        return;
    }
    ll mid=l+r>>1;
    build(index<<1,l,mid);
    build(index<<1|1,mid+1,r);
    tree[index].maxn=max(tree[index<<1].maxn,tree[index<<1|1].maxn);
}
void push_down(int index)
{
    if(tree[index].a==1&&tree[index].b==0)return;
    tree[index<<1].a*=tree[index].a;
    tree[index<<1].b=tree[index<<1].b*tree[index].a+tree[index].b;
    tree[index<<1].maxn=tree[index<<1].maxn*tree[index].a+tree[index].b;
    tree[index<<1|1].a*=tree[index].a;
    tree[index<<1|1].b=tree[index<<1|1].b*tree[index].a+tree[index].b;
    tree[index<<1|1].maxn=tree[index<<1|1].maxn*tree[index].a+tree[index].b;
    tree[index].a=1;tree[index].b=0;
}
void update(int index,ll l,ll r,ll x,ll y)
{
    if(tree[index].l>=l&&tree[index].r<=r)
    {
        tree[index].a*=x;tree[index].b=tree[index].b*x+y;
        tree[index].maxn=tree[index].maxn*x+y;
        return;
    }
    push_down(index);
    if(tree[index<<1].r>=l)update(index<<1,l,r,x,y);
    if(tree[index<<1|1].l<=r)update(index<<1|1,l,r,x,y);
    tree[index].maxn=max(tree[index<<1].maxn,tree[index<<1|1].maxn);
}
ll query(int index,ll l,ll r)
{
    if(tree[index].l>=l&&tree[index].r<=r)
    {
        return tree[index].maxn;
    }
    push_down(index);
    ll ans=-1e18;
    if(tree[index<<1].r>=l)ans=max(ans,query(index<<1,l,r));
    if(tree[index<<1|1].l<=r)ans=max(ans,query(index<<1|1,l,r));
    return ans;
}
int main( )
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;cin>>n;ll m;cin>>m;
    for(int i=1;i<=n;i++)cin>>arr[i];
    build(1,1,n);
    ll flag,l,r,K;
    while(m--)
    {
        cin>>flag;
        if(flag==1)
        {
            cin>>l>>r>>K;
            update(1,l,r,0,K);
        }
        else if(flag==2)
        {
            cin>>l>>r>>K;
            update(1,l,r,1,K);
        }
        else{
            cin>>l>>r;
            cout<<query(1,l,r)<<endl;
        }
    }
    return 0;
}

by O_v_O @ 2024-01-30 10:58:40

@timmyliao 谢谢

by timmyliao @ 2024-01-30 13:28:34

希望能够关注我，谢谢