rt，最近在学习分块，用分块写的，部分参考第三篇题解

#include<bits/stdc++.h>
#define MOD 571373 
using namespace std;
void IOS()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	return;
}
int n,m,p,sqn,x,y,z,cnt;
int bg[325],ed[325],sm[325],ml[325],pl[325];
int c[100005];
void print()
{
	cout<<"c:"<<endl;
	for(int i=1;i<=n;i++) cout<<c[i]<<" ";
	cout<<endl;
	cout<<" bgn   end   sum   mul   pls"<<endl;
	for(int i=1;i<=cnt;i++)
		cout<<setw(5)<<bg[i]<<" "<<setw(5)<<ed[i]<<" "<<setw(5)<<sm[i]<<" "<<setw(5)<<ml[i]<<" "<<setw(5)<<pl[i]<<endl;
	return;
}
void rst(int kkk)
{
	for(int i=bg[kkk];i<=ed[kkk];i++)
		c[i]=(c[i]*ml[kkk]+pl[kkk])%MOD;
	ml[kkk]=1,pl[kkk]=0;
	return;
}
int main()
{
	IOS();
	cin>>n>>m>>p;
	sqn=sqrt(n);
	for(int i=1;i<=sqn;i++)
	{
		bg[i]=(i-1)*sqn+1;
		ed[i]=i*sqn;
		ml[i]=1;
	}
	if(sqn*sqn<n)
	{
		bg[sqn+1]=sqn*sqn+1;
		ed[sqn+1]=n;
		ml[sqn+1]=1;
	}
	cnt=1;
	for(int i=1;i<=n;i++)
	{
		cin>>c[i];
		if(i>ed[cnt]) cnt++;
		//bl[i]=cnt;
		sm[cnt]+=c[i];
	}
	while(m--)
	{
		cin>>p>>x>>y;
		int kkk=ceil(1.0*x/sqn),cz=ceil(1.0*y/sqn);
		if(p==1)
		{
			cin>>z;
			rst(kkk);
			for(int i=x;i<=min(y,ed[kkk]);i++)
			{
				sm[kkk]=(sm[kkk]+(z-1)*c[i])%MOD;
				c[i]=(c[i]*z)%MOD;
			}
			if(kkk!=cz)
				for(int i=bg[cz];i<=y;i++)
				{
					sm[cz]=(sm[cz]+(z-1)*c[i])%MOD;
					c[i]=(c[i]*z)%MOD;
				}
			for(int i=kkk+1;i<=cz-1;i++)
			{
				ml[i]=ml[i]*z%MOD;
				pl[i]=pl[i]*z%MOD;
			}
		}
		else if(p==2)
		{
			cin>>z;
			for(int i=x;i<=min(ed[kkk],y);i++)
				c[i]=(c[i]+z)%MOD;
			sm[kkk]=(sm[kkk]+z*(min(ed[kkk],y)-x+1))%MOD;
			if(kkk!=cz)
			{
				for(int i=bg[cz];i<=y;i++) c[i]=(c[i]+z)%MOD;
				sm[cz]=(sm[cz]+z*(y-bg[cz]+1))%MOD;
			}
			for(int i=kkk+1;i<=cz-1;i++) pl[i]=(pl[i]+z)%MOD;
		}
		else
		{
			int nm=0;
			for(int i=x;i<=min(ed[kkk],y);i++)
				nm=(nm+c[i]*ml[kkk]+pl[kkk])%MOD;
			if(kkk!=cz)
				for(int i=bg[cz];i<=y;i++)
					nm=(nm+c[i]*ml[cz]+pl[cz])%MOD;
			for(int i=kkk+1;i<cz;i++)
				nm=(nm+sm[i]*ml[i]+(ed[i]-bg[i]+1)*pl[i])%MOD;
			cout<<nm<<endl;
		}
		//print();
	}
	return 0;
}