題目鏈接：http://poj.org/problem?id=3468 求的是給定區間段的值，或者直接更新某一段的值，也就是線段樹的成段更新，成段更新是需要一個懶惰標記的，也就是說，如果要更新某一個區間段，當更新到這個區間段的時候，就停止在這里，給這個區間段做一個標記，不往下更新，只有再次更新到這個區間的子區間的時候，才更新到下面，同時標記下放且原標記清零，如果詢問的區間是這個區間的子區間，也標記下放且清零，這樣一來大大地節省了時間消耗。
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cmath>
5 #include <algorithm>
6 #include <cstring>
7 using namespace std;
8 #define lson l, m, rt << 1
9 #define rson m + 1, r, rt << 1 | 1
10 const int maxn = 100010;
11 long long sum[maxn << 2], add[maxn << 2];
12 void PushUp(int rt)
13 {
14 sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
15 }
16 void PushDown(int rt, int m)
17 {
18 if (add[rt])
19 {
20 add[rt << 1] += add[rt];
21 add[rt << 1 | 1] += add[rt];
22 sum[rt << 1] += add[rt] * (m - (m >> 1));
23 sum[rt << 1 | 1] += add[rt] * (m >> 1);
24 add[rt] = 0;
25 }
26 }
27 void build(int l, int r, int rt)
28 {
29 if (l == r)
30 {
31 scanf("%lld", &sum[rt]);
32 return;
33 }
34 int m = (l + r) >> 1;
35 build(lson);
36 build(rson);
37 PushUp(rt);
38 }
39 void update(int ll, int rr, int c, int l, int r, int rt)
40 {
41 if (ll <= l && rr >= r)
42 {
43 add[rt] += c;
44 sum[rt] += (long long)c * (r - l + 1);
45 return;
46 }
47 PushDown(rt, r - l + 1);
48 int m = (l + r) >> 1;
49 if (ll <= m) update(ll, rr, c, lson);
50 if (rr > m) update(ll, rr, c, rson);
51 PushUp(rt);
52 }
53 long long query(int ll, int rr, int l, int r, int rt)
54 {
55 if (ll <= l && rr >= r) return sum[rt];
56 PushDown(rt, r - l + 1);
57 int m = (l + r) >> 1;
58 long long ret = 0;
59 if (ll <= m) ret += query(ll, rr, lson);
60 if (rr > m) ret += query(ll, rr, rson);
61 return ret;
62 }
63 int main()
64 {
65 int m, n;
66 while(scanf("%d%d", &n, &m) != EOF)
67 {
68 build(1, n, 1);
69 char c[2];
70 while(m--)
71 {
72 scanf("%s", c);
73 if (c[0] == 'Q')
74 {
75 int x, y;
76 scanf("%d%d", &x, &y);
77 long long ans = query(x, y, 1, n, 1);
78 printf("%lld\n", ans);
79 }
80 if (c[0] == 'C')
81 {
82 int x, y, z;
83 scanf("%d%d%d", &x, &y, &z);
84 update(x, y, z, 1, n, 1);
85 }
86 }
87 }
88 return 0;
89
|