POJ3468 线段树 + Lazy Tag (延迟标记)

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
#define REP(i, a, b) for (LL i = (a), _end_ = (b); i <= _end_; ++i)
#define DREP(i, a, b) for (LL i = (a), _begin_ = (b); i >= _begin_; --i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (LL((x).size()))
#define ALL(x) (x).begin(), (x).end()
template<typename T> inline bool chkmin(T &a, const T &b){ return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b){ return a < b ? a = b, 1 : 0; }
typedef long long LL;
const LL dmax = 100100 << 2, oo = 0x3f3f3f3f;
LL n, m;
LL a[dmax];
LL c[dmax], add[dmax];
#define left x << 1, l, mid
#define right x << 1 | 1, mid + 1, r
inline LL Mid(LL x, LL y){ return (x + y) >> 1; }
inline void push_up(LL x){
c[x] = c[x << 1] + c[x << 1 | 1]; }
inline void push_down(LL x, LL y)
{
if (add[x])
{
add[x << 1] += add[x];
add[x << 1 | 1] += add[x];
c[x << 1] += (y - (y >> 1)) * add[x];
c[x << 1 | 1] += (y >> 1) * add[x];
add[x] = 0;
}
}
void create(LL x, LL l, LL r)
{
if (l == r)
{
scanf("%I64d", &c[x]);
return;
}
LL mid = Mid(l, r);
create(left);
create(right);
push_up(x);
}
void update(LL x, LL l, LL r, LL s, LL t, LL k)
{
if (l >= s && r <= t)
{
add[x] += k;
c[x] += (LL)k * (r - l + 1);
return;
}
LL mid = Mid(l, r);
push_down(x, r - l + 1);
if (s <= mid)
update(left, s, t, k);
if (t > mid)
update(right, s, t, k);
push_up(x);
}
LL query(LL x, LL l, LL r, LL s, LL t)
{
if (l >= s && r <= t)
return c[x];
push_down(x, r - l + 1);
LL mid = Mid(l, r);
LL sum = 0;
if (s <= mid) sum += query(left, s, t);
if (mid < t) sum += query(right, s, t);
return sum;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%I64d%I64d", &n, &m);
create(1, 1, n);
getchar();
REP(i, 1, m)
{
LL c = getchar(), x, y;
scanf("%I64d%I64d", &x, &y);
if (c == 'Q')
printf("%I64dn", query(1, 1, n, x, y));
else{
LL z;
scanf("%I64d", &z);
update(1, 1, n, x, y, z);
}
getchar();
}
return 0;
}