分块求条

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e5+15;
int n,cnt,block;
int a[maxn],L[maxn],R[maxn],pos[maxn],sum[maxn],add[maxn];
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if (ch=='-') {f=-1;}ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return f*x;
}
void build()
{
    block=sqrt(n);
    while(1)
    {
        cnt++;
        L[cnt]=(cnt-1)*block+1;
        R[cnt]=cnt*block;
        if (R[cnt]>=n)
        {
            R[cnt]=n;
            break;
        }
    }
    for (int i=1;i<=cnt;++i)
    {
        int cur=0;
        for (int j=L[i];j<=R[i];++j)
        {
            cur+=a[j];
            pos[j]=i;
        }
        sum[i]=cur;
    }
}
void update(int l,int r,int x)
{
    if (pos[l]==pos[r])
    {
        for (int i=l;i<=r;++i) a[i]+=x;
        sum[pos[l]]+=(r-l+1)*x;
        return ;
    }
    for (int i=l;i<=R[pos[l]];++i) a[i]+=x;
    for (int i=L[pos[r]];i<=r;++i) a[i]+=x;
    sum[pos[l]]+=(R[pos[l]]-l+1)*x;
    sum[pos[r]]+=(r-L[pos[r]]+1)*x;
    for (int i=pos[l]+1;i<=pos[r]-1;++i) add[i]+=x;
}
int query(int l,int r,int m)
{
    int ans=0;
    if (pos[l]==pos[r])
    {
        for (int i=l;i<=r;++i) ans=(ans+a[i])%m;
        return (ans+(r-l+1)*add[pos[l]]%m)%m;
    }
    for (int i=l;i<=R[pos[l]];++i) ans=(ans+a[i])%m;
    ans=(ans+(R[pos[l]]-l+1)*add[pos[l]]%m)%m;
    for (int i=L[pos[r]];i<=r;++i) ans=(ans+a[i])%m;
    ans=(ans+(r-L[pos[r]]+1)*add[pos[r]]%m)%m;
    for (int i=pos[l]+1;i<=pos[r]-1;++i) ans=(ans+sum[i]+add[i]*(R[i]-L[i]+1)%m)%m;
    return ans;
}
signed main()
{
    n=read();
    for (int i=1;i<=n;++i) a[i]=read();
    build();
//  for (int i=1;i<=cnt;++i) cout<<sum[i]<<' ';
    for (int i=1;i<=n;++i)
    {
        int opt=read(),l=read(),r=read(),c=read();
        if (opt==0) update(l,r,c);
        else cout<<query(l,r,c+1)<<"\n";
    }
    return 0;
}