POJ 3468 A Simple Problem with Integers

这个题目涉及到线段树的成段更新，中间需要注意变量的类型是 __int64,update函数用来更新[L，R]区间的数，当L<=l&&R>=r时，可以不向下更新，将增加值c存储在记录该节点的对应区间应该增加量的变量中，也就是进行color[rt]+=c操作，等到下次更新该区间时向下更新或者查询区间和时更新。

顺便提醒一下自己：以后遇到用long long ，__int64的题目里面变量最好统一一个类型，不然很容易混淆。

代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define N 100010
 4 #define maxn (1<<20)
 5 #define lson l,m,rt<<1
 6 #define rson m+1,r,rt<<1|1
 7 
 8 typedef __int64  ll;
 9 ll sum[maxn];
10 ll  ab[N],color[maxn];
11 
12 void PushUp(ll rt)
13 {
14     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
15 }
16 
17 void build(ll l,ll r,ll rt)
18 {
19     if(l==r)
20     {
21         sum[rt]=ab[l];
22         return;
23     }
24     ll m=(l+r)>>1;
25     build(lson);
26     build(rson);
27     PushUp(rt);
28 }
29 
30 void PushDown(ll rt,ll m)/*用于向下更新*/
31 {
32     if(color[rt])
33     {
34         color[rt<<1]+=color[rt];/*对增量进行积累*/
35         color[rt<<1|1]+=color[rt];
36         sum[rt<<1]+=(m-(m>>1))*color[rt];
37         sum[rt<<1|1]+=(m>>1)*color[rt];
38         color[rt]=0;
39     }
40 }
41 
42 void update(ll L,ll R,ll c,ll l,ll r,ll rt)
43 {
44     if(L<=l&&R>=r)
45     {
46         sum[rt]+=(r-l+1)*c;
47         color[rt]+=c;
48         return;
49     }
50     PushDown(rt,r-l+1);
51     int m=(l+r)>>1;
52     if(L<=m)
53         update(L,R,c,lson);
54     if(R>m)
55         update(L,R,c,rson);
56     PushUp(rt);
57 }
58 
59 ll query(ll L,ll R,ll l,ll r,ll rt)
60 {
61     if(L<=l&&R>=r)
62         return sum[rt];
63     ll res=0;
64     ll m=(l+r)>>1;
65     PushDown(rt,r-l+1);
66     if(L<=m)
67         res+=query(L,R,lson);
68     if(R>m)
69         res+=query(L,R,rson);
70     return res;
71 }
72 
73 int main(void)
74 {
75     ll n,q,i,a,b,c;
76     char op[3];
77     while(scanf("%lld%lld",&n,&q)!=EOF)
78     {
79         memset(color,0,sizeof(color));
80         for(i=1; i<=n; i++)
81             scanf("%lld",ab+i);
82         build(1,n,1);
83         while(q--)
84         {
85             scanf("%s%lld%lld",op,&a,&b);
86             if(op[0]=='C')
87             {
88                 scanf("%lld",&c);
89                 update(a,b,c,1,n,1);
90             }
91             else
92             {
93                 printf("%lld
",query(a,b,1,n,1));
94             }
95         }
96     }
97 }