50分求助,这里的inf足够大,但是还是50分

P1253 扶苏的问题

zyzbldnb @ 2023-01-16 21:00:04


#include<bits/stdc++.h>                
using namespace std;
typedef long long ll;
const int maxn=1e+6,inf=0x3f3f3f3f3f;
ll t1[4*maxn+5],t2[4*maxn+5],w[4*maxn+5],a[maxn];
int n,q;
bool c[4*maxn+5];
void build(int u,int l,int r)
{
    if(r==l) 
    {w[u]=a[l];return;}
    int mid=(l+r)/2;
    build(2*u,l,mid);
    build(2*u+1,mid+1,r);
    w[u]=max(w[2*u],w[2*u+1]);
}
void tag1(int u,int x) //= 赋值x
{
    t1[u]=x;c[u]=1;
    t2[u]=0; // 覆盖掉了
    w[u]=x;
}
void tag2(int u,int x)//+x
{ 
     if(c[u]!=0) t1[u]+=x;
     else t2[u]+=x;  
     w[u]+=x;   // 最大值加x
}
void pushdown(int u)
{
   if(c[u]!=0) // 赋值了
   {
    tag1(2*u,t1[u]);tag1(2*u+1,t1[u]);//一定要优先t1,是覆盖,没有覆盖才是+
    c[u]=0;//
   }
   else {
    tag2(2*u,t2[u]);
    tag2(2*u+1,t2[u]);
    t2[u]=0;
   }
}
int query(int u,int l,int r, int x,int y)
{
     if(x<=l&&r<=y) return w[u]; 
     else if(!(x>r||y<l) )
     {
        int mid=(l+r)/2;    
        pushdown(u);
         return max(query(2*u,l,mid,x,y),query(2*u+1,mid+1,r,x,y));
     } 
     else return -inf;  
}
void update(int u,int l,int r,int x, int y, int xx,int opt)
{
    if(x<=l&&r<=y) 
     {
        if(opt==1) tag1(u,xx);
        if(opt==2) tag2(u,xx);
     }
    else if(!(x>r||y<l) )
    {
        pushdown(u);
        int mid=(l+r)>>1;
         update(2*u,l,mid,x,y,xx,opt);
         update(2*u+1,mid+1,r,x,y,xx,opt);
         w[u]=max(w[2*u],w[2*u+1]);
    }
}
int main()
{
    int opt,x,y;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        scanf("%ld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d%d",&opt,&x,&y);
        if(opt!=3)
        {
            int xx;
            scanf("%d",&xx);
            update(1,1,n,x,y,xx,opt);
        }
        else printf("%ld\n",query(1,1,n,x,y));
    }
    return 0;
}
```cpp

|