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 <cstdio>
using namespace std;
typedef long long LL;
const int N = 1 << 20;
int n, m, tot = 1;
struct node
{
LL s, sz, tag;
} tr[N];
void build()
{
while (tot <= n)
tot <<= 1;
for (int i = 1; i <= n; i++)
{
scanf("%lld", &tr[i + tot].s);
tr[i + tot].sz = 1;
}
for (int i = tot - 1; i; i--)
{
tr[i].s = tr[i << 1].s + tr[i << 1 | 1].s;
tr[i].sz = tr[i << 1].sz + tr[i << 1 | 1].sz;
}
}
void modify(int l, int r, LL k)
{
int szx = 0, szy = 0;
for (l += tot, r += tot; l ^ r ^ 1; l >>= 1, r >>= 1)
{
tr[l].s += k * szx;
if (!(l & 1))
{
tr[l + 1].tag += k;
szx += tr[l + 1].sz;
tr[l + 1].s += tr[l + 1].sz * k;
}
tr[r].s += k * szy;
if (r & 1)
{
tr[r - 1].tag += k;
szy += tr[r - 1].sz;
tr[r - 1].s += tr[r - 1].sz * k;
}
}
for (; l && r; l >>= 1, r >>= 1)
{
tr[l].s += k * szx;
tr[r].s += k * szy;
}
}
LL query(int l, int r)
{
LL res = 0, szx = 0, szy = 0;
for (l += tot, r += tot; l ^ r ^ 1; l >>= 1, r >>= 1)
{
res += tr[l].tag * szx + tr[r].tag * szy;
if (!(l & 1))
{
res += tr[l + 1].s;
szx += tr[l + 1].sz;
}
if (r & 1)
{
res += tr[r - 1].s;
szy += tr[r - 1].sz;
}
}
for (; l && r; l >>= 1, r >>= 1)
res += tr[l].tag * szx + tr[r].tag * szy;
return res;
}
int main()
{
scanf("%d%d", &n, &m);
build();
for (int op, l, r; m; m--)
{
scanf("%d%d%d", &op, &l, &r);
if (op == 1)
{
int k;
scanf("%d", &k);
modify(l - 1, r + 1, k);
}
else if (op == 2)
printf("%lld\n", query(l - 1, r + 1));
}
return 0;
}
|