块儿外的元素还是暴力
为了快速求答案，要提前预处理每个块儿的元素和
区间修改的时候，不完整的块儿直接修改，顺便更新元素和
完整的块儿还是打标记
1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 using namespace std; 5 long long read() 6 { 7 long long x=0,f=1;char ch=getchar(); 8 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 9 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 10 return x*f; 11 } 12 const int maxn=50005; 13 int n,blo; 14 int bl[maxn]; 15 long long v[maxn],atag[maxn],sum[maxn]; 16 void add(int a,int b,int c) 17 { 18 for(int i=a;i<=min(bl[a]*blo,b);i++) 19 v[i]+=c,sum[bl[a]]+=c; 20 if(bl[a]!=bl[b]) 21 for(int i=(bl[b]-1)*blo+1;i<=b;i++) 22 v[i]+=c,sum[bl[b]]+=c; 23 for(int i=bl[a]+1;i<=bl[b]-1;i++) atag[i]+=c; 24 } 25 long long query(int a,int b) 26 { 27 long long ans=0; 28 for(int i=a;i<=min(bl[a]*blo,b);i++) 29 ans+=v[i]+atag[bl[a]]; 30 if(bl[a]!=bl[b]) 31 for(int i=(bl[b]-1)*blo+1;i<=b;i++) 32 ans+=v[i]+atag[bl[b]]; 33 for(int i=bl[a]+1;i<=bl[b]-1;i++) 34 ans+=sum[i]+blo*atag[i]; 35 return ans; 36 } 37 int main() 38 { 39 n=read();blo=sqrt(n); 40 for(int i=1;i<=n;i++) v[i]=read(); 41 for(int i=1;i<=n;i++) 42 { 43 bl[i]=(i-1)/blo+1; 44 sum[bl[i]]+=v[i]; //预处理 45 } 46 for(int i=1;i<=n;i++) 47 { 48 int f=read(),a=read(),b=read(),c=read(); 49 if(f==0) add(a,b,c); 50 if(f==1) printf("%d ",query(a,b)%(c+1)); 51 } 52 return 0; 53 }