记录

调试时，将块长 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;
}