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
86
87
88
89
| #include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define MS 100009
#define INF 20000009
#define mod 1000000007
#define Pi acos(-1.0)
#define Pair pair<LL,LL>
LL n,m,k;
LL p[MS<<2];
LL la[MS<<2];
bool in(int L,int l,int r,int R){
return (l<=r) && (L<=l) && (r<=R);
}
void push_up(int rt){
p[rt] = p[ls] + p[rs];
}
void push_down(int rt,int l,int r){
if(la[rt]){
int m = l+r >> 1;
p[ls] += la[rt]*(m-l+1);
p[rs] += la[rt]*(r-m);
la[ls] += la[rt];
la[rs] += la[rt];
la[rt] = 0;
}
}
void update(int L,int R,int l,int r,int rt,LL val){
if(in(L,l,r,R)){
p[rt] += (r-l+1)*val;
la[rt] += val;
return;
}
push_down(rt,l,r);
int m = l+r>>1;
if(m >= L) update(L,R,l,m,ls,val);
if(m < R) update(L,R,m+1,r,rs,val);
push_up(rt);
}
LL get_sum(int L,int R,int l,int r,int rt){
if(in(L,l,r,R)){
return p[rt];
}
push_down(rt,l,r);
LL cc = 0;
int m = l+r>>1;
if(m >= L) cc += get_sum(L,R,l,m,ls);
if(m < R) cc += get_sum(L,R,m+1,r,rs);
return cc;
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=1;i<=n;i++){
LL x;
cin >> x;
update(i,i,1,n,1,x);
}
while(m--){
LL op,l,r,val;
cin >> op >> l >> r;
if(op == 2){
LL ans = get_sum(l,r,1,n,1);
cout << ans << endl;
}
else if(op == 1){
cin >> val;
update(l,r,1,n,1,val);
}
}
return 0;
}
|
