POJ3468 A Simple Problem with Integers

解题思路：线段树区间更新模板题，注意比较与点更新的区别。不解释，上代码：
 1 #include<cstdio>
 2 using namespace std;
 3 #define lson l, m, rt << 1
 4 #define rson m+1, r, rt << 1 | 1
 5 #define LL long long
 6 #define maxn 100005
 7 LL sum[maxn<<2], add[maxn<<2];
 8 
 9 void PushUp(int rt)
10 {
11     sum[rt] = sum[rt<<1] + sum[rt<<1 | 1];
12 }
13 
14 void PushDown(int rt, int m)
15 {
16     if(add[rt])
17     {
18         add[rt<<1] += add[rt];
19         add[rt<<1|1] += add[rt];
20         sum[rt<<1] += (m - (m>>1)) * add[rt];
21         sum[rt<<1|1] += (m >> 1) * add[rt];
22         add[rt] = 0;
23     }
24     return ;
25 }
26 
27 void Build(int l, int r, int rt)
28 {
29     add[rt] = 0;
30     if(l == r)
31     {
32         scanf("%I64d", &sum[rt]);
33         return ;
34     }
35     int m = (l + r) >> 1;
36     Build(lson);
37     Build(rson);
38     PushUp(rt);
39 }
40 
41 LL Query(int L, int R, int l, int r, int rt)
42 {
43     if(L <= l && R >= r) return sum[rt];
44     PushDown(rt, r-l+1);
45     int m = (l + r) >> 1;
46     LL ret = 0;
47     if(L <= m) ret += Query(L, R, lson);
48     if(R > m) ret += Query(L, R, rson);
49     return ret;
50 }
51 
52 void Update(int L, int R, int c, int l, int r, int rt)
53 {
54     if(L <= l && R >= r)
55     {
56         add[rt] += c;
57         sum[rt] += (LL)c * (r - l + 1);
58         return ;
59     }
60     PushDown(rt, r - l + 1);
61     int m = (l + r) >> 1;
62     if(L <= m) Update(L, R, c, lson);
63     if(R > m) Update(L, R, c, rson);
64     PushUp(rt);
65 }
66 
67 int main()
68 {
69     int n, m, a, b, c;
70     char str[5];
71     scanf("%d %d", &n, &m);
72     Build(1, n, 1);
73     while(m--)
74     {
75         scanf("%s", str);
76         if(str[0] == 'Q')
77         {
78             scanf("%d %d", &a, &b);
79             LL ans = Query(a, b, 1, n, 1);
80             printf("%I64d
", ans);
81         }
82         else
83         {
84             scanf("%d %d %d", &a, &b, &c);
85             Update(a, b, c, 1, n, 1);
86         }
87     }
88     return 0;
89 }
View Code