hdu1698 区间更新

 1 #include<queue>
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<map>
 7 #include<cmath>
 8 #include<string>
 9 #include<vector>
10 #include<functional>
11 #define inf 0x3f3f3f3f
12 #define mem(k,b) memset(k,b,sizeof(k))
13 #define ll long long
14 #define ls (x)<<1
15 #define rs (x)<<1|1
16 #define lson ls,l,mid
17 #define rson rs,mid+1,r
18 using namespace std;
19 const int maxn = 100010;
20 
21 int t, n, m, q, p, z;
22 int tree[maxn << 2], add[maxn << 2];
23 
24 void pushup(int x) {
25     tree[x] = tree[ls] + tree[rs];
26     return;
27 }
28 
29 void pushdown(int x, int len){
30     if (add[x]){
31         add[ls] = add[x];
32         add[rs] = add[x];
33         tree[ls] = add[x] * (len - (len >> 1));
34         tree[rs] = add[x] * (len >> 1);
35         add[x] = 0;
36     }
37 }
38 
39 void build(int x, int l, int r){
40     add[x] = 0;
41     if (l == r){
42         tree[x] = 1;
43         return;
44     }
45     int mid = (l + r) >> 1;
46     build(lson); build(rson);
47     pushup(x);
48 }
49 
50 void xiugai(int x, int l, int r, int l1, int r1,int zhi1){
51     if (l >= l1 && r<=r1){
52         add[x] = zhi1;
53         tree[x] = zhi1*(r - l + 1);
54         return;
55     }
56     pushdown(x, r - l + 1);
57     int mid = (l + r) >> 1;
58     if (r1<= mid){
59         xiugai(lson, l1, r1, zhi1);
60     }
61     else if (l1>mid){
62         xiugai(rson, l1, r1, zhi1);
63     }
64     else{
65         xiugai(lson, l1, mid, zhi1);
66         xiugai(rson, mid + 1, r1, zhi1);
67     }
68     pushup(x);
69 }
70 
71 int main(){
72     int c = 1;
73     scanf("%d",&t);
74     while (t--){
75         scanf("%d%d",&n,&m);
76         build(1, 1, n);
77         for (int i = 0; i < m; i++){
78             scanf("%d%d%d",&q,&p,&z);
79             xiugai(1, 1, n, q, p, z);
80         }
81         printf("Case %d: The total value of the hook is %d.\n",c++,tree[1]);
82     }
83     return 0;
84 }