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
|
#include<cstdio>
#define N 100005
using namespace std;
long long tree[N << 2] = {0}, add[N << 2] = {0};
int n, m, bit;
inline long long () {
char e = getchar();
long long s = 0, k = 0;
while ((e < '0' || e > '9') && e != '-')e = getchar();
if (e == '-')k = 1, e = getchar();
while (e >= '0' && e <= '9')s = s * 10 + e - '0', e = getchar();
return k ? -s : s;
}
inline void build(int x) {
for (bit = 1; bit <= x + 1; bit <<= 1);
for (int i = bit + 1; i <= bit + x; i++)tree[i] = read();
for (int i = bit - 1; i; i--)tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
inline void modify(int x, long long k) {
for (int i = bit + x; i; i >>= 1)tree[i] += k;
}
inline void modify(int l, int r, long long k) {
if (l == r) {
modify(l, k);
return;
}
int lNum = 0, rNum = 0, num = 1, s, t;
for (s = bit + l - 1, t = bit + r + 1; s ^ t ^ 1; s >>= 1, t >>= 1, num <<= 1) {
tree[s] += k * lNum, tree[t] += k * rNum;
if (~s & 1)add[s ^ 1] += k, tree[s ^ 1] += k * num, lNum += num;
if (t & 1)add[t ^ 1] += k, tree[t ^ 1] += k * num, rNum += num;
}
for (; s; s >>= 1, t >>= 1)tree[s] += lNum * k, tree[t] += rNum * k;
}
inline long long query(int l, int r) {
long long ans = 0;
int lNum = 0, rNum = 0, num = 1, s, t;
for (s = bit + l - 1, t = bit + r + 1; s ^ t ^ 1; s >>= 1, t >>= 1, num <<= 1) {
if (add[s])ans += add[s] * lNum;
if (add[t])ans += add[t] * rNum;
if (~s & 1)ans += tree[s ^ 1], lNum += num;
if (t & 1)ans += tree[t ^ 1], rNum += num;
}
for (; s; s >>= 1, t >>= 1)ans += add[s] * lNum, ans += add[t] * rNum;
return ans;
}
int main() {
n = read(), m = read();
build(n);
for (int i = 1; i <= m; i++) {
long long a, b, c;
if (read() == 1)a = read(), b = read(), c = read(), modify(a, b, c);
else a = read(), b = read(), cout << query(a, b) << endl;
}
return 0;
}
|
近期评论