https://www.luogu.com.cn/discuss/show/300375
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
typedef long long ll;
ll a[N],sum[N],add[N];
int n,m,B;
int get(int x)
{
return (x+B-1)/B;
}
signed main()
{
cin>>n>>m;
B=sqrt(n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[get(i)]+=a[i];
}
while(m--)
{
int op,l,r,x;
cin>>op>>l>>r;
int idl=get(l),idr=get(r);
if(op==1)
{
cin>>x;
if(idl==idr)
{
for(int i=l;i<=r;i++)
{
a[i]*=x;
a[i]%=10007;
}
sum[idl]*=(r-l+1)*x;
sum[idl]%=10007;
}
else
{
for(int i=idl+1;i<=idr-1;i++)
{
add[i]*=x;
add[i]%=10007;
}
for(int i=l;i<=idl*B;i++)
{
a[i]*=x;
a[i]%=10007;
}
sum[idl]+=(idl*B-l+1)*x;
for(int i=(idr-1)*B+1;i<=r;i++)
{
a[i]*=x;
a[i]%=10007;
}
sum[idr]+=(r-(idr-1)*B)*x;
sum[idr]%=10007;
}
}
else if(op==0)
{
cin>>x;
if(idl==idr)
{
for(int i=l;i<=r;i++)
{
a[i]+=x;
a[i]%=10007;
}
sum[idl]+=(r-l+1)*x;
sum[idl]%=10007;
}
else
{
for(int i=idl+1;i<=idr-1;i++)
{
add[i]+=x;
add[i]%=10007;
}
for(int i=l;i<=idl*B;i++)
{
a[i]+=x;
a[i]%=10007;
}
sum[idl]+=(idl*B-l+1)*x;
sum[idl]%=10007;
for(int i=(idr-1)*B+1;i<=r;i++)
{
a[i]+=x;
a[i]%=10007;
}
sum[idr]+=(r-(idr-1)*B)*x;
}
}
else if(op==2)
{
cout<<a[r]+add[get(r)]<<"\n";
}
}
}