hdu 1698 Just a Hook

http://acm.hdu.edu.cn/showproblem.php?pid=1698
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 100010
 5 #define ll __int64
 6 using namespace std;
 7 
 8 int n,x1,x2,c,m;
 9 struct node
10 {
11     int l,r;
12     int cover;
13 } tree[maxn*4];
14 
15 void build(int i,int l,int r)
16 {
17     tree[i].l=l;
18     tree[i].r=r;
19     tree[i].cover=1;
20     if(l==r) return ;
21     int mid=(l+r)>>1;
22     build(i<<1,l,mid);
23     build(i<<1|1,mid+1,r);
24 }
25 
26 void down(int i)
27 {
28     if(tree[i].l==tree[i].r) return ;
29     if(tree[i].cover!=-1)
30     {
31         tree[i<<1].cover=tree[i].cover;
32         tree[i<<1|1].cover=tree[i].cover;
33         tree[i].cover=-1;
34     }
35 }
36 void update(int i,int l,int r,int c)
37 {
38     if(tree[i].cover==c) return;
39     if(tree[i].l==l&&tree[i].r==r)
40     {
41         tree[i].cover=c;
42         return ;
43     }
44     down(i);
45     int mid=(tree[i].l+tree[i].r)>>1;
46     if(r<=mid)
47     {
48         update(i<<1,l,r,c);
49     }
50     else if(l>mid)
51     {
52         update(i<<1|1,l,r,c);
53     }
54     else
55     {
56         update(i<<1,l,mid,c);
57         update(i<<1|1,mid+1,r,c);
58     }
59 }
60 
61 ll search1(int i)
62 {
63     if(tree[i].cover!=-1)
64     {
65         return (tree[i].r-tree[i].l+1)*tree[i].cover;
66     }
67     down(i);
68     return search1(i<<1)+search1(i<<1|1);
69 }
70 int main()
71 {
72     int t;
73     scanf("%d",&t);
74     int cas=1;
75     while(t--)
76     {
77         scanf("%d",&n);
78         scanf("%d",&m);
79         build(1,1,n);
80         for(int i=1; i<=m; i++)
81         {
82             scanf("%d%d%d",&x1,&x2,&c);
83             update(1,x1,x2,c);
84         }
85         printf("Case %d: The total value of the hook is %I64d.
",cas,search1(1));
86         cas++;
87     }
88     return 0;
89 }
View Code