HDOJ1698解题报告【线段树模板】

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

题目概述：

　　一段区间从1~n，每次操作将某一段全部改为x，操作完成后求整个区间和。

大致思路：

　　典型的一个RMQ模板题。只需要注意add操作里pushdown的+=改成=就可以了。

　　　　还有注意在build_tree的时候初始化整棵树！！！

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <vector>
 6 #include <ctime>
 7 #include <map>
 8 #include <queue>
 9 #include <cstring>
10 #include <algorithm>
11 using namespace std;
12 
13 #define sacnf scanf
14 #define scnaf scanf
15 #define maxn 100010
16 #define maxm 26
17 #define inf 1061109567
18 #define Eps 0.001
19 const double PI=acos(-1.0);
20 #define mod 1000000007
21 #define MAXNUM 10000
22 void Swap(int &a,int &b) {int t=a;a=b;b=t;}
23 int Abs(int x) {return (x<0)?-x:x;}
24 typedef long long ll;
25 typedef unsigned int uint;
26 
27 struct node
28 {
29     int val,add;
30 } tree[4*maxn];
31 
32 void build_tree(int l,int r,int dir)
33 {
34     tree[dir].add=tree[dir].val=0;
35     if(l==r)
36     {
37         tree[dir].val=1;
38         return;
39     }
40     int m=(l+r)>>1;
41     build_tree(l,m,dir*2);
42     build_tree(m+1,r,dir*2+1);
43     tree[dir].val=tree[dir*2].val+tree[dir*2+1].val;
44 }
45 
46 void push(int l,int r,int dir)
47 {
48     if(tree[dir].add)
49     {
50         tree[dir*2].add=tree[dir*2+1].add=tree[dir].add;
51         tree[dir*2].val=(((l+r)>>1)-l+1)*tree[dir].add;
52         tree[dir*2+1].val=(r-((l+r)>>1))*tree[dir].add;
53         tree[dir].add=0;
54     }
55 }
56 
57 void Modify(int l,int r,int dir,int ql,int qr,int c)
58 {
59     if(qr<l||r<ql) return;
60     if(ql<=l&&r<=qr)
61     {
62         tree[dir].add=c;
63         tree[dir].val=(r-l+1)*c;
64         return;
65     }
66     push(l,r,dir);
67     int m=(l+r)>>1;
68     Modify(l,m,dir*2,ql,qr,c);
69     Modify(m+1,r,dir*2+1,ql,qr,c);
70     tree[dir].val=tree[dir*2].val+tree[dir*2+1].val;
71 }
72 
73 int main()
74 {
75     //freopen("data.in","r",stdin);
76     //freopen("data.out","w",stdout);
77     //clock_t st=clock();
78     int T,n;scanf("%d",&T);
79     for(int kase=1;kase<=T;kase++)
80     {
81         scanf("%d",&n);
82         build_tree(1,n,1);
83         int m,x,y,z;
84         scnaf("%d",&m);
85         while(m--)
86         {
87             scanf("%d%d%d",&x,&y,&z);
88             Modify(1,n,1,x,y,z);
89         }
90         printf("Case %d: The total value of the hook is %d.
",kase,tree[1].val);
91     }
92     //clock_t ed=clock();
93     //printf("

Time Used : %.5lf Ms.
",(double)(ed-st)/CLOCKS_PER_SEC);
94     return 0;
95 }