（线段树）Just a Hook -- hdu -- 1689

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1698

思路：

我的想法很简单，像上一题一样从后面向前面来算，前面已经覆盖的，后面自然不能再来计算了，具体是每次都计算覆盖的总长度，然后用这次的总长度减上次的总长度，自然就得到了这次覆盖的长度，可能我的方法不是很好吧！不过这是自己想出来的，再去借鉴一下别人的代码，多种想法是好的，毕竟是自己做的，因为数据不是很大所以不用离散化就可以

代码：

  1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<stdlib.h>
  4 #include<string.h>
  5 using namespace std;
  6 
  7 #define Lson r<<1
  8 #define Rson r<<1|1
  9 
 10 const int N = 100005;
 11 
 12 struct Node
 13 {
 14     int L, R, e;
 15 } s[N<<2];
 16 
 17 struct node
 18 {
 19     int L, R;
 20     int len; //len里面要记录被覆盖的长度
 21     int Mid()
 22     {
 23         return (L+R)>>1;
 24     }
 25 } a[N<<2];
 26 
 27 void UpDate(int r)
 28 {
 29     if(a[r].L != a[r].R)
 30         a[r].len = a[Lson].len + a[Rson].len;
 31 }
 32 
 33 void BuildTree(int r, int L, int R)
 34 {
 35     a[r].L = L, a[r].R = R;
 36     a[r].len = 0;
 37 
 38     if(L==R) return ;
 39 
 40     BuildTree(Lson, L, a[r].Mid());
 41     BuildTree(Rson, a[r].Mid()+1, R);
 42 }
 43 
 44 int Insert(int r, int L, int R)
 45 {
 46     if(a[r].L<=L && a[r].R>=R && a[r].len == a[r].R-a[r].L+1)
 47         return a[r].len;
 48     if(a[r].L==L && a[r].R==R)
 49     {
 50         a[r].len = R-L+1;
 51         return a[r].len;
 52     }
 53 
 54     if(R<=a[r].Mid())
 55         Insert(Lson, L, R);
 56     else if(L>a[r].Mid())
 57         Insert(Rson, L, R);
 58     else
 59     {
 60         Insert(Lson, L, a[r].Mid());
 61         Insert(Rson, a[r].Mid()+1, R);
 62     }
 63 
 64     UpDate(r);
 65 
 66     return a[r].len;
 67 }
 68 
 69 int main()
 70 {
 71     int t, k=1;
 72     scanf("%d", &t);
 73     while(t--)
 74     {
 75         int n, m;
 76         scanf("%d%d", &n, &m);
 77 
 78         BuildTree(1, 1, n);
 79 
 80         for(int i=2; i<=m+1; i++)
 81             scanf("%d%d%d", &s[i].L, &s[i].R, &s[i].e);
 82 
 83         s[1].L = 1, s[1].R = n, s[1].e = 1;
 84 
 85 
 86         int sum = 0, z=0, w=0;
 87         for(int i=m+1; i>0; i--)
 88         {
 89             w = z;
 90             z = Insert(1, s[i].L, s[i].R);
 91 
 92             sum += (z-w)*s[i].e;
 93 
 94             if(z==n)
 95                 break;
 96         }
 97 
 98         printf("Case %d: The total value of the hook is %d.
", k++, sum);
 99 
100     }
101     return 0;
102 }

代码：

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<string.h>
 4 #include<algorithm>
 5 using namespace std;
 6 #define Lson root<<1,L,tree[root].Mid()
 7 #define Rson root<<1|1,tree[root].Mid()+1,R
 8 
 9 const int maxn = 100005;
10 
11 struct Hook{int l, r, z;}hook[maxn];
12 struct Tree{
13     int L, R;
14     int isCover;//等于1的时候被覆盖，等于2的时候区间下面有被覆盖的
15     int Mid(){return (L+R)/2;}
16     int Len(){return (R-L+1);}
17 }tree[maxn*4];
18 
19 void Build(int root, int L, int R)
20 {
21     tree[root].L = L, tree[root].R = R;
22     tree[root].isCover = false;
23 
24     if(L == R)return ;
25 
26     Build(Lson);
27     Build(Rson);
28 }
29 void Up(int root)
30 {
31     if(tree[root].L != tree[root].R)
32     if(tree[root<<1].isCover == 1 && tree[root<<1|1].isCover == 1)
33         tree[root].isCover = 1;
34 }
35 int  Insert(int root, int L, int R)
36 {
37     if(tree[root].isCover == 1)return 0;
38 
39     if(tree[root].L == L && tree[root].R == R && !tree[root].isCover)
40     {
41         tree[root].isCover = 1;
42         return tree[root].Len();
43     }
44     tree[root].isCover = 2;
45 
46     int ans = 0;
47 
48     if(R <= tree[root].Mid())
49         ans = Insert(root<<1, L, R);
50     else if(L > tree[root].Mid())
51         ans = Insert(root<<1|1, L, R);
52     else
53         ans = Insert(Lson)+Insert(Rson);
54 
55     Up(root);
56 
57     return ans;
58 }
59 
60 int main()
61 {
62     int i, T, t=1;
63 
64     scanf("%d", &T);
65 
66     while(T--)
67     {
68         int N, M;
69 
70         scanf("%d%d", &N, &M);
71         Build(1, 1, N);
72 
73         for(i=1; i<=M; i++)
74             scanf("%d%d%d", &hook[i].l, &hook[i].r, &hook[i].z);
75 
76         int ans = N;
77 
78         for(i=M; i>0; i--)
79         {
80             int len = Insert(1, hook[i].l, hook[i].r);
81             ans = ans - len + len * hook[i].z;
82         }
83 
84         printf("Case %d: The total value of the hook is %d.
", t++, ans);
85     }
86 
87     return 0; }

勿忘初心