E - Just a Hook HDU - 1698

 1 #include <cmath>
 2 #include <queue>
 3 #include <string>
 4 #include <cstdio>
 5 #include <cstring>
 6 #include <iostream>
 7 #include <algorithm>
 8 #define forn(i,n) for (int i = 0; i < (n); i++)
 9 #define forab(i,a,b) for (int i = (a); i <= (b); i++)
10 #define forba(i,b,a) for (int i = (b); i >= (a); i--)
11 #define mset(a,n) memset(a,n,sizeof(a))
12 #define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
13 #define P pair<int,int>
14 #define fi first
15 #define se second
16 using namespace std;
17 #define N 100005
18 #define inf 0x3f3f3f3f
19 #define ll long long
20 struct SegmentTree
21 {
22     int l,r;
23     ll data;
24     ll add;
25     #define l(x) t[x].l
26     #define r(x) t[x].r
27     #define data(x) t[x].data
28     #define add(x) t[x].add
29 } t[N * 4 + 5];
30 ll n,m,cnt;
31 void build(int p,int l,int r)
32 {
33     l(p) = l;
34     r(p) = r;
35     add(p) = 0;
36     if(l==r)
37     {
38         data(p) = 1;
39         return;
40     }
41     int m = (l + r) / 2;
42     int ls = 2 * p,rs = 2 * p + 1;
43     build(ls,l,m);
44     build(rs,m + 1,r);
45     data(p) = data(ls) + data(rs);
46 }
47 void spread(int p)
48 {
49     if(add(p))
50     {
51         data(2 * p) = add(p) * (r(2 * p) - l(2 * p) + 1);
52         data(2 * p + 1) = add(p) * (r(2 * p + 1) - l(2 * p + 1) + 1);
53         add(2 * p) = add(p);
54         add(2 * p + 1) = add(p);
55         add(p) = 0;
56     }
57 }
58 void change(int p,int r,int d)
59 {
60     if(l<=l(p)&&r>=r(p))
61     {
62         data(p) = (r(p) - l(p) + 1) * d;
63         add(p) = d;
64         return;
65     }
66     spread(p);
67     int m = (l(p) + r(p)) / 2;
68     int ls = 2 * p,rs = 2 * p + 1;
69     if(l<=m)
70         change(ls,r,d);
71     if(r>m)
72         change(rs,d);
73     data(p) = data(ls) + data(rs);
74 }
75 int main()
76 {
77     fast;
78     cin >> cnt;
79     forab(cas,1,cnt)
80     {
81         cin >> n >> m;
82         build(1,n);
83         forab(i,m)
84         {
85             int x,y,z;
86             cin >> x >> y >> z;
87             change(1,x,z);
88         }
89         cout << "Case " << cas << ": The total value of the hook is " <<t[1].data<< "." << endl;
90     }
91 }
92 /*
93 1
94 10
95 2
96 1 5 2
97 5 9 3
98  */