poj3468A Simple Problem with Integers(成段操作）

http://acm.sdut.edu.cn/bbs/read.php?tid=5651

。。本来只会向上更新现在学习了如何向下更新延迟标记法。。。使复杂度降低

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 using namespace std;
 5 #define max 100000
 6 __int64 s[max*4],te[max*4];
 7 void pushup(int w)
 8 {
 9     s[w] = s[2*w]+s[2*w+1];
10 }
11 void pushdown(int w,int m)
12 {
13     if(te[w])
14     {
15         te[2*w]+=te[w];
16         te[2*w+1] += te[w];
17         s[2*w] += (te[w]*(m-(m/2)));
18         s[2*w+1]+=(te[w]*(m/2));
19         te[w] = 0;//将延迟标记去除
20     }
21 }
22 void build(int l,int r,int w)
23 {
24     te[w] = 0;
25     if(l==r)
26     {
27         scanf("%I64d",&s[w]);
28         return ;
29     }
30     int m = (l+r)/2;
31     build(l,m,2*w);
32     build(m+1,r,2*w+1);
33     pushup(w);
34 }
35 void add(int a,int b,int da,int l,int r,int w)
36 {
37     if(a<=l&&b>=r)
38     {
39         te[w] += da;//多次延迟标记
40         s[w]+=da*(r-l+1);
41         return ;
42     }
43     pushdown(w,r-l+1);//更新
44     int m = (l+r)/2;
45     if(a<=m)
46     add(a,b,da,l,m,2*w);
47     if(b>m)
48     add(a,b,da,m+1,r,2*w+1);
49     pushup(w);
50 }
51 __int64 search(int a,int b,int l,int r,int w)
52 {
53     if(a<=l&&b>=r)
54     {
55         return s[w];
56     }
57     pushdown(w,r-l+1);
58     int m=(l+r)/2;
59     __int64 re = 0;
60     if(a<=m)
61     re+=search(a,b,l,m,2*w);
62     if(b>m)
63     re+=search(a,b,m+1,r,2*w+1);
64     return re;
65 }
66 int main()
67 {
68     int i,j,k,n,m,t,a,b,c;
69     char z;
70     scanf("%d%d",&n,&m);
71     build(1,n,1);
72     while(m--)
73     {
74         scanf("%*c%c",&z);
75         if(z=='Q')
76         {
77             scanf("%d%d",&a,&b);
78             printf("%I64d\n",search(a,b,1,n,1));
79         }
80         else
81         {
82             scanf("%d%d%d",&a,&b,&c);
83             add(a,b,c,1,n,1);
84         }
85     }
86     return 0;
87 }