题目链接:http://poj.org/problem?id=3468 求的是给定区间段的值,或者直接更新某一段的值,也就是线段树的成段更新,成段更新是需要一个懒惰标记的,也就是说,如果要更新某一个区间段,当更新到这个区间段的时候,就停止在这里,给这个区间段做一个标记,不往下更新,只有再次更新到这个区间的子区间的时候,才更新到下面,同时标记下放且原标记清零,如果询问的区间是这个区间的子区间,也标记下放且清零,这样一来大大地节省了时间消耗。
![](/Images/OutliningIndicators/ContractedBlock.gif) 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
|