Hdu 1698 【线段树成段更新】.cpp

题意：

　　动态更新一段区间的值..

　　最后输出总区间的和..

思路：

　　其实就是线段树的成段更新..

　　用到了lazy[] 表示懒惰标志..

　　懒惰标记：

　　　　就是每次更新不更新到最后..而是更新到包含了区间的最大的节点..

　　　　然后如果下次更新的时候更新到了上次已经更新到的节点..

　　　　那先把上次更新暂停的节点往下更新..直到这次更新的区间最大的节点没有被标记..

　　　这样就省时间了..

Tips：

　　　　pushdown节点就是用来向下更新的..

　　　　要注意的是modify函数..即每次更新的时候把根节点标记为要更新的数 x

　　　　然后顺便求出最大值sum[rt]..

　　　　同时原节点要还原为非标记状态-1

　　　　然后向下pushdown 范围是 R-L+1

Code:

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 const int MAXN = 100010;
 5 int sum[MAXN<<2];
 6 int lazy[MAXN<<2];
 7 
 8 void pushup(int rt)
 9 {
10     sum[rt] = sum[rt<<1] + sum[rt<<1|1];
11 }
12 
13 void pushdown(int rt, int x)
14 {
15     if(lazy[rt] != -1) {
16         lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
17         sum[rt<<1] = (x-(x>>1))*lazy[rt];///!!!
18         sum[rt<<1|1] = (x>>1)*lazy[rt];///!!!
19         lazy[rt] = -1;
20     }
21 }
22 
23 void creat(int l, int r, int rt)
24 {
25     lazy[rt] = -1, sum[rt] = 1;
26     if(l == r) return;
27     int mid = (l+r)>>1;
28     creat(l, mid, rt<<1);
29     creat(mid+1, r, rt<<1|1);
30     pushup(rt);
31 }
32 
33 void modify(int l, int r, int x, int L, int R, int rt)
34 {
35     if(l <= L && r >= R) {
36         lazy[rt] = x;
37         sum[rt] = x*(R-L+1);///!!!
38         return;
39     }
40     pushdown(rt, R-L+1);///!!!
41     int mid = (L+R)>>1;
42     if(l <= mid) modify(l, r, x, L, mid, rt<<1);
43     if(r > mid) modify(l, r, x, mid+1, R, rt<<1|1);
44     pushup(rt);
45 }
46 
47 int main()
48 {
49     int i, j, k = 0;
50     int n, T, q;
51     int x, y, w;
52     while(scanf("%d", &T) != EOF)
53     while(T--)
54     {
55         scanf("%d %d", &n, &q);
56         creat(1, n, 1);
57 
58         while(q--) {
59             scanf("%d %d %d", &x, &y, &w);
60             modify(x, y, w, 1, n, 1);
61         }
62 
63         printf("Case %d: The total value of the hook is %d.\n", ++k, sum[1]);
64     }
65     return 0;
66 }

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1698

Hdu 1698 【线段树 成段更新】.cpp

Hdu 1698 【线段树成段更新】.cpp