(Juan Feng) : 一定可以卡过去的！
- 数列长度是(N)，把一列数分成(sqrt{N})个块，基于分治策略完成。
- (Sum[i]) 第(i)块中数的和
- (Tag[i])第(i)块中数字被整体修改的值
- (A[i])暴力维护即可。
#include <string.h>
#include <stdio.h>
#include <math.h>
#define GC getchar()
#define Clean(X,K) memset(X,K,sizeof(X))
const int Maxn = 100005 , MaxR = 320 ;
int N , M , Rt , Belong[Maxn];
long long A[Maxn] ;
long long Qread () {
long long X = 0 ;
char C = GC ;
while (C > '9' || C < '0') C = GC ;
while (C >='0' && C <='9') {
X = X * 10 + C - '0' ;
C = GC ;
}
return X ;
}
struct Block {
int Left , Right ;
long long Tag , Sum ;
};
Block B[MaxR] ;
long long Ask (int L , int R) {
int St = Belong[L] , Ed = Belong[R] ;
long long Ans = 0 ;
if (St == Ed) {
for (int i = L ; i <= R ; ++ i) Ans += A[i] ;
Ans += B[St].Tag * (R - L + 1) ;
return Ans ;
}
for (int i = L ; i <= B[St].Right ; ++ i) Ans += A[i] ;
Ans += B[St].Tag * (B[St].Right - L + 1) ;
for (int i = B[Ed].Left ; i <= R ; ++ i) Ans += A[i] ;
Ans += B[Ed].Tag * (R - B[Ed].Left + 1) ;
for (int i = St + 1 ; i < Ed ; ++ i) Ans += B[i].Sum ;
return Ans ;
}
void Add (int L , int R , long long int K) {
int St = Belong[L] , Ed = Belong[R] ;
if (St == Ed) {
B[St].Sum += (R - L + 1) * K ;
for (int i = L ; i <= R ; ++ i) A[i] += K ;
return ;
}
B[St].Sum += (B[St].Right - L + 1) * K ;
B[Ed].Sum += (R - B[Ed].Left + 1) * K ;
for (int i = L ; i <= B[St].Right ; ++ i) A[i] += K ;
for (int i = B[Ed].Left ; i <= R ; ++ i) A[i] += K ;
for (int i = St+ 1 ; i < Ed ; ++ i) {
B[i].Sum += Rt * K ;
B[i].Tag += K ;
}
}
int main () {
// freopen ("P3372.txt" , "r" , stdin) ;
// freopen ("my.out" , "w" , stdout) ;
N = Qread () , M = Qread () ;
Rt = sqrt ((double)N) + 1 , Clean(Belong , 0) , Clean(B , 0);
for (int i = 1 ; i <= N; ++ i) A[i] = Qread () ;
for (int i = 0 ; i <= Rt; ++ i) {
B[i].Left = i * Rt + 1, B[i].Right = B[i].Left + Rt - 1 ;
for (int j = B[i].Left ; j <= B[i].Right&&j <= N ; ++ j) Belong[j] = i , B[i].Sum += A[j];
}
for (int i = 1 ; i <= M ; ++ i) {
int Q = Qread () , L = Qread () , R = Qread ();
if (Q == 2) printf ("%lld
" , Ask (L , R)) ;
else {
long long K = Qread () ;
Add (L , R , K) ;
}
}
fclose (stdin) , fclose (stdout) ;
return 0 ;
}