POJ-3468

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
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
namespace
{
typedef long long ll;
const int MAX_N = (1 << 18) - 1;
int n, N, Q, a, b, c;
ll da[MAX_N], db[MAX_N];
void add(int k, int l, int r)
{
if (a <= l && r <= b)
da[k] += c;
else if (!(b <= l || a >= r))
{
db[k] += (min(r, b) - max(l, a)) * c;
add(k * 2 + 1, l, (l + r) / 2);
add(k * 2 + 2, (l + r) / 2, r);
}
}
ll sum(int k, int l, int r)
{
if (b <= l || a >= r)
return 0;
else if (a <= l && r <= b)
return (r - l) * da[k] + db[k];
else
{
ll res = (min(r, b) - max(l, a)) * da[k];
res += sum(k * 2 + 1, l, (l + r) / 2);
res += sum(k * 2 + 2, (l + r) / 2, r);
return res;
}
}
ll init(int k)
{
if (k >= n - 1)
return db[k];
else
return db[k] = init(2 * k + 1) + init(2 * k + 2);
}
void input()
{
memset(da, 0, sizeof(da));
memset(db, 0, sizeof(db));
scanf("%d %d", &N, &Q);
n = 1;
while (n < N)
n <<= 1;
for (int i = 0; i < N; i++)
scanf("%lld", &db[i + n - 1]);
init(0);
char s[2];
while (Q--)
{
scanf("%s", s);
if (s[0] == 'Q')
{
scanf("%d %d", &a, &b);
a--;
printf("%lldn", sum(0, 0, n));
}
else
{
scanf("%d %d %d", &a, &b, &c);
a--;
add(0, 0, n);
}
}
}
}
int main()
{
input();
return 0;
}