分块50pts WA求条

代码

#include<bits/stdc++.h>
#include<algorithm>
#define int long long
typedef long long lli;
typedef double lf;
using namespace std;
const lli MAX_=-LONG_LONG_MAX;
lli n,block,tot;
lli a[1003007];
lli l[100007],r[100007],be[1003007],lazy[100007],mx[100007];
void build()
{
    for(int i=0;i<=100005;i++)mx[i]=MAX_;
    block=sqrt(n),tot=n/block;
    if(n%block)tot++;
    for(int i=1;i<=tot;i++)
        l[i]=(i-1)*block+1,r[i]=i*block;
    r[tot]=n;
    for(int i=1;i<=n;i++)
        be[i]=(i-1)/block+1;
    for(int i=1;i<=tot;i++)
        for(int j=l[i];j<=r[i];j++)
            mx[i]=max(mx[i],a[j]);
}
void upd(int x,int y,lli k)
{
    if(be[x]==be[y])
    {
        for(int i=x;i<=y;i++)
            a[i]+=k,mx[be[i]]=max(mx[be[i]],a[i]+lazy[be[i]]);
        return;
    }
    for(int i=x;i<=r[be[x]];i++)
        a[i]+=k,mx[be[i]]=max(mx[be[i]],a[i]+lazy[be[i]]);
    for(int i=l[be[y]];i<=y;i++)
        a[i]+=k,mx[be[i]]=max(mx[be[i]],a[i]+lazy[be[i]]);
    for(int i=be[x]+1;i<=be[y]-1;i++)
        lazy[i]+=k,mx[i]+=k;
}
void cover_(int x,int y,lli k)
{
    if(be[x]==be[y])
    {
        for(int i=x;i<=y;i++)
            a[i]=k-lazy[be[i]];
        mx[be[x]]=max(mx[be[x]],k);
        return;
    }
    for(int i=x;i<=r[be[x]];i++)
        a[i]=k-lazy[be[i]];
    mx[be[x]]=max(mx[be[x]],k);
    for(int i=l[be[y]];i<=y;i++)
        a[i]=k-lazy[be[i]];
    mx[be[y]]=max(mx[be[y]],k);
    for(int i=be[x]+1;i<=be[y]-1;i++)
        lazy[i]=k-a[i],mx[i]=k;
}
lli query(int x,int y)
{
    lli mx1=MAX_;
    if(be[x]==be[y])
    {
        for(int i=x;i<=y;i++)
            mx1=max(mx1,a[i]+lazy[be[i]]);  
        return mx1;
    }
    for(int i=x;i<=r[be[x]];i++)
        mx1=max(mx1,a[i]+lazy[be[i]]);
    for(int i=l[be[y]];i<=y;i++)
        mx1=max(mx1,a[i]+lazy[be[i]]);
    for(int i=be[x]+1;i<=be[y]-1;i++)
        mx1=max(mx1,mx[i]);
    return mx1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    //freopen("P1253_6.in","r",stdin);
    //freopen("fout.txt","w",stdout);
    int q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build();
    while(q--)
    {
        lli x,y,k,op;
        scanf("%lld%lld%lld",&op,&x,&y);
        if(op==3)
            printf("%lld\n",query(x,y));
        else if(op==2)
        {
            scanf("%lld",&k);
            upd(x,y,k);
        }
        else 
        {
            scanf("%lld",&k);
            cover_(x,y,k);
        }/*
        for(int i=1;i<=n;i++)
            cout<<a[i]+lazy[be[i]]<<" ";
        cout<<endl;
        for(int i=1;i<=tot;i++)
            cout<<mx[i]<<" ";
        cout<<endl;*/
    }
}