1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| #include <iostream>
#include <cstdio>
using namespace std;
const int inf=1e5+7;
template <typename _TP>
inline void read(_TP &X){
char ch;int w;X=0;
while(!isdigit(ch)){w=ch=='-';ch=getchar();}
while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^48);ch=getchar();}
X=w?-X:X;
}
struct node{
int l,r;
long long sum,lag;
}t[inf<<2];
int a[inf];
inline void push_down(const int k){
t[k<<1].lag+=t[k].lag;
t[k<<1|1].lag+=t[k].lag;
t[k<<1].sum+=t[k].lag*(t[k<<1].r-t[k<<1].l+1);
t[k<<1|1].sum+=t[k].lag*(t[k<<1|1].r-t[k<<1|1].l+1);
t[k].lag=0;
}
void build(const int k,const int l,const int r){
t[k].l=l;
t[k].r=r;
if(l==r){
t[k].sum=a[l];
return;
}
int m=(l+r)>>1;
build(k<<1,l,m);
build(k<<1|1,m+1,r);
t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
}
void change(const int k,const int l,const int r,const int x){
if(t[k].l>=l && t[k].r<=r){
t[k].lag+=x;
t[k].sum+=x*(t[k].r-t[k].l+1);
return;
}
if(t[k].lag)push_down(k);
int m=(t[k].l+t[k].r)>>1;
if(l<=m)change(k<<1,l,r,x);
if(r>m)change(k<<1|1,l,r,x);
t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
}
long long ans;
void sum(const int k,const int l,const int r){
if(t[k].l>=l && t[k].r<=r){
ans+=t[k].sum;
return;
}
if(t[k].lag)push_down(k);
int m=(t[k].r+t[k].l)>>1;
if(l<=m)sum(k<<1,l,r);
if(r>m)sum(k<<1|1,l,r);
}
int main(){
long long n,x,l,r,q;
int opt;
read(n);read(q);
for(int i=1;i<=n;i++){
read(a[i]);
}
build(1,1,n);
while(q--){
read(opt);
switch(opt){
case 1:{
read(l);read(r);read(x);
change(1,l,r,x);
break;
}
case 2:{
read(l);read(r);
ans=0;
sum(1,l,r);
cout<<ans<<"\n";
break;
}
}
}
return 0;
}
|
