线段树20pts求调,悬关

P1253 扶苏的问题

shysacscsc @ 2023-11-14 11:23:08


#include<iostream>

using namespace std;
typedef long long ll;
const int maxnn=1e6;
const ll INF=-LLONG_MAX;
struct node
{
    int l,r;
    ll lazy,maxn;
    ll add;
};
int n,q;
int a[maxnn];
node tr[4*maxnn];
void pushup(int u)
{
    tr[u].maxn=max(tr[u<<1].maxn,tr[u<<1|1].maxn);
}
void build(int u,int l,int r)
{   tr[u].l=l,tr[u].r=r,tr[u].lazy=INF,tr[u].add=0;//表示不需要改
    if(tr[u].l==tr[u].r)
    {
        tr[u].maxn=a[l];
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void pushdown(int u)
{
    if(tr[u].lazy!=INF)
    {
        tr[u<<1].maxn=tr[u].lazy;
        tr[u<<1|1].maxn=tr[u].lazy;
        tr[u<<1].lazy=tr[u].lazy;
        tr[u<<1|1].lazy=tr[u].lazy;
        tr[u<<1].add=tr[u<<1|1].add=0;
        tr[u].lazy=INF;
    }
    else if(tr[u].add!=0)
    { if(tr[u<<1].lazy!=INF)
        {
            tr[u<<1].lazy+=tr[u].add;
            tr[u<<1].maxn+=tr[u].add;
        }
        if(tr[u<<1|1].lazy!=INF)
        {
            tr[u<<1|1].lazy+=tr[u].add;
            tr[u<<1|1].maxn+=tr[u].add;
        }
        if(tr[u<<1].lazy==INF)
        {
            tr[u<<1].maxn+=tr[u].add;
            tr[u<<1].add+=tr[u].add;
        }
        if(tr[u<<1|1].lazy==INF)
        {
            tr[u<<1|1].add+=tr[u].add;
            tr[u<<1|1].maxn+=tr[u].add;
        }
        tr[u].add=0;
    }
}
void modify(int u,int l,int r,int p)//修改
{
    if(tr[u].l>=l&&tr[u].r<=r)
    {
        tr[u].maxn=p;
        tr[u].add=0;
        tr[u].lazy=p;
        return;
    }
    pushdown(u);
    int mid=tr[u].r+tr[u].l>>1;
    if(l<=mid) modify(u<<1,l,r,p);
    if(r>mid) modify(u<<1|1,l,r,p);
    pushup(u);
}
void modify2(int u,int l,int r,int p)//增加
{
    if(tr[u].l>=l&&tr[u].r<=r)
    {  if(tr[u].lazy==INF)
        {
            tr[u].maxn+=p;
            tr[u].add+=p;
        }
        if(tr[u].lazy!=INF)
        {
            tr[u].lazy+=p;
            tr[u].maxn+=p;
        }
        return;
    }
    pushdown(u);
    int mid=tr[u].r+tr[u].l>>1;
    if(l<=mid) modify2(u<<1,l,r,p);
    if(r>mid) modify2(u<<1|1,l,r,p);
    pushup(u);
}
ll query(int u,int l,int r)
{   ll res=INF;
    if(tr[u].l>=l&&tr[u].r<=r)
    {
        return  tr[u].maxn;
    }
    pushup(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) res=max(res, query(u<<1,l,r));
    if(r>mid)  res=max(res, query(u<<1|1,l,r));
    return res;
}
int main()
{    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);
    while (q--)
    {
        int opt,a,b,c,d;
        cin>>opt;
        if(opt==1)
        {
            cin>>a>>b>>c;
            modify(1,a,b,c);
        }
        if(opt==2)
        {
            cin>>a>>b>>c;
            modify2(1,a,b,c);
        }
        if(opt==3)
        {
            cin>>a>>b;
            cout<<query(1,a,b)<<endl;
        }
    }
} ```

|