分块维护一个区间和
然后记得更新的时候左边角块的tag不要打错到右边角块
#include#include #include #include using namespace std;long long sz,num,n,belong[50100],a[50100],sum[50100],tag[50100];void calbe(int n){ for(int i=1;i<=n;i++) belong[i]=(i-1)/sz+1;}void reset(int x){ sum[x]=0; for(int i=(x-1)*sz+1;i<=min(x*sz,n);i++) sum[x]+=a[i];}void update(int l,int r,int w){ int xl=belong[l]; int xr=belong[r]; for(int i=l;i<=min(xl*sz,(long long)r);i++){ a[i]+=w; sum[xl]+=w; } if(xl!=xr){ for(int i=(xr-1)*sz+1;i<=r;i++){ a[i]+=w; sum[xr]+=w; } } for(int i=xl+1;i<=xr-1;i++){ tag[i]+=w; }}long long query(int l,int r,int w){ int xl=belong[l]; int xr=belong[r]; long long ans=0; for(int i=l;i<=min(xl*sz,(long long)r);i++) ans=(ans%w+(a[i]+tag[xl])%w)%w; if(xl!=xr){ for(int i=(xr-1)*sz+1;i<=r;i++) ans=(ans%w+(a[i]+tag[xr])%w)%w; } for(int i=xl+1;i<=xr-1;i++) ans=(ans%w+(sum[i]+(tag[i]*sz))%w)%w; return ans;}int main(){ scanf("%lld",&n); sz=sqrt(n); num=n/sz; calbe(n); if(n%sz) num++; for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=num;i++) reset(i);// for(int i=1;i<=num;i++)// printf("%d\n",sum[i]); for(int i=1;i<=n;i++){ int opt,l,r,c; scanf("%d %d %d %d",&opt,&l,&r,&c); if(opt==0) update(l,r,c); else printf("%lld\n",query(l,r,c+1)); } return 0;}