【題目敘述】https://vjudge.net/problem/HDU-1698
【解題想法】線段樹 (Segment Tree)，區間修改 + 懶標記 (Lazy Tag)
- 留意：本題有多筆測資，每次要記得先初始化lazy tag。
- lazy[n<<2]：紀錄各區間的metallic sticks材料(c)。
- 每次update時，完全被 [ul, ur] 覆蓋的區間，對應節點的區間和更新為「區間長度」* c。其餘部分覆蓋的區間，update之前要進行push，處理先前留下的lazy tag。
- 本題進行多次update，但只做一次query，最後直接印出total[1]即是答案。
#include <iostream>
#include <cstring>
using namespace std;
int t, n, q, a, b, c, d;
int total[100005 << 2], lazy[100005 << 2];
void pull(int x){
total[x] = total[x<<1] + total[x<<1|1];
}
void push(int x, int l, int r){
if (lazy[x] == 0) return;
int mid = (l + r) >> 1;
lazy[x<<1] = lazy[x];
total[x<<1] = lazy[x] * (mid - l + 1);
lazy[x<<1|1] = lazy[x];
total[x<<1|1] = lazy[x] * (r - mid);
lazy[x] = 0;
}
void build(int x, int l, int r){
if (l == r){
total[x] = 1;
return;
}
int mid = (l + r) >> 1;
build(x<<1, l, mid);
build(x<<1|1, mid+1, r);
pull(x);
}
void update(int x, int l, int r, int ul, int ur){
if (ul <= l && r <= ur){
lazy[x] = c;
total[x] = c * (r-l+1);
return;
}
push(x, l, r);
int mid = (l + r) >> 1;
if (ul <= mid) update(x<<1, l, mid, ul, ur);
if (mid < ur) update(x<<1|1, mid+1, r, ul, ur);
pull(x);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t;
for (int Case = 1; Case <= t; Case++){
memset(lazy, 0, sizeof(lazy));
cin >> n;
build(1, 1, n);
cin >> q;
for (int i = 0; i < q; i++){
cin >> a >> b >> c;
update(1, 1, n, a, b);
}
cout << "Case " << Case << ": The total value of the hook is " << total[1] << ".\n";
}
}