分块求调

记录

调试时，将块长 len 改为 n 时就没有WA，只有AC和TLE，证明对整块的处理没有问题，但是散块的处理却出现了问题，求大佬调试。

#include<bits/stdc++.h>
using namespace std;
#define CONNECT_BASE(x,y) x##y
#define CONNECT(x,y) CONNECT_BASE(x,y)
#define DEBUG_BASE(x) cerr<<#x<<'='<<x<<' '
#define DEB_1(x) DEBUG_BASE(x)
#define DEB_2(x,y) DEB_1(x),DEB_1(y)
#define DEB_3(x,y,z) DEB_1(x),DEB_2(y,z)
#define DEB_4(x,y,z,w) DEB_1(x),DEB_3(y,z,w)
#define DEB_5(a,b,c,d,e) DEB_1(a),DEB_4(b,c,d,e)
#define DEB_6(a,b,c,d,e,f) DEB_1(a),DEB_5(b,c,d,e,f)
#define COUNT_BASE(_1,_2,_3,_4,_5,_6,x,...) x
#define COUNT(...) COUNT_BASE(__VA_ARGS__,6,5,4,3,2,1,0)
#define D(...) std::cerr << "[In Line " << __LINE__ << "]: ",CONNECT(DEB_,COUNT(__VA_ARGS__))(__VA_ARGS__) , cerr << '\n'
#define nhd std::cerr << "nahida\n";
#define ll long long
#define pb push_back
#define lll __int128
#define lb lower_bound
#define ld long double
#define cnl cout<<endl;
#define R(i,n) for(int i=1;i<=n;i++)
const ll INF=LLONG_MAX;
const int N=1e6+10;
template <typename T>
inline void read(T &x)
{
   T s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   x=s*w;
}
template <typename T>
inline void write(T x)
{
    if(x<0) {
        putchar('-');
        x = -x;
    }
    if(x>9) write(x / 10);
    putchar(x % 10 + '0');
}
int n,len;
ll a[N],block[N],tag[N],id[N];
void build()
{
    fill(block,block+n+5,-INF);
    len=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        id[i]=(i-1)/len+1;
        block[id[i]]=max(block[id[i]],a[i]);
    }
}
void pushdown(int k)
{
    if(tag[k]!=0)
    {
        for(int i=(k-1)*len+1;i<=k*len;i++)
        {
            a[i]=tag[k];
        }
        tag[k]=0;
    }
}
void rebuild(int k)
{
    block[k]=-INF;
    for(int i=(k-1)*len+1;i<=k*len;i++)
    {
        block[k]=max(block[k],a[i]);
    }
}
void add(int l,int r,ll w)
{
    int p1=id[l],p2=id[r];
    pushdown(p1);pushdown(p2);
    if(p1==p2)
    {
        for(int i=l;i<=r;i++)
        {
            a[i]+=w;
        }
        rebuild(p1);
        return ;
    }
    for(int i=l;i<=p1*len;i++)
    {
        a[i]+=w;
    }
    rebuild(p1);
    for(int i=(p2-1)*len+1;i<=min(r,n);i++)
    {
        a[i]+=w;
    }
    rebuild(p2);
    for(int i=p1+1;i<=p2-1;i++)
    {
        block[i]+=w;
        tag[i]+=w;
    }
}
void change(int l,int r,ll w)
{
    int p1=id[l],p2=id[r];
    pushdown(p1);pushdown(p2);
    if(p1==p2)
    {
        for(int i=l;i<=r;i++)
        {
            a[i]=w;
        }
        rebuild(p1);
        return ;
    }
    for(int i=l;i<=p1*len;i++)
    {
        a[i]=w;
    }
    rebuild(p1);
    for(int i=(p2-1)*len+1;i<=min(r,n);i++)
    {
        a[i]=w;
    }
    rebuild(p2);
    for(int i=p1+1;i<=p2-1;i++)
    {
        block[i]=w;
        tag[i]=w;
    }
}
ll query(int l,int r)
{
    int p1=id[l],p2=id[r];
    pushdown(p1);pushdown(p2);
    ll ans=-INF;
    if(p1==p2)
    {
        for(int i=l;i<=r;i++)
        {
            ans=max(ans,a[i]);
        }
        return ans;
    }
    for(int i=l;i<=p1*len;i++)
    {
        ans=max(ans,a[i]);
    }
    for(int i=(p2-1)*len+1;i<=min(r,n);i++)
    {
        ans=max(ans,a[i]);
    }
    for(int i=p1+1;i<=p2-1;i++)
    {
        ans=max(ans,block[i]);
    }
    return ans;
}
signed main()
{
    int q;
    read(n);read(q);
    R(i,n) read(a[i]);
    build();
    while(q--)
    {
        int op,l,r;
        read(op);read(l);read(r);
        if(op==1)
        {
            int x;
            read(x);
            change(l,r,x);
        }
        else if(op==2)
        {
            int x;
            read(x);
            add(l,r,x);
        }
        else if(op==3)
        {
            write(query(l,r));
            putchar('\n');
        }
//      R(i,n) cerr<<a[i]<<' ';
//      cerr<<endl;
    }
    return 0;
}