思路: 线段树 (区间更新)
区间更新模板
把 插入
操作 换成 更新
操作;
代码实现:
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
#define lson rt<<1
#define rson rt<<1|1
#define mid (l+r)>>1
const int N = 1e5 + 10;
int _, n, m;
typedef long long ll;
ll tr[N << 2], lz[N << 2];
void up(int rt) {
tr[rt] = tr[lson] + tr[rson];
}
void down(int rt, int l, int r) {
if (lz[rt] != 0) {
int m = mid;
lz[lson] = lz[rt];
tr[lson] = (m - l + 1) * lz[rt];
lz[rson] = lz[rt];
tr[rson] = (r - m) * lz[rt];
lz[rt] = 0;
}
}
void insert(int rt, int l, int r, int x, int y, ll v) {
if (l == x && r == y) {
tr[rt] = (r - l + 1) * v;
lz[rt] = v;
return;
}
down(rt, l, r);
int m = mid;
if (y <= m)
insert(lson, l, m, x, y, v);
else if (x > m)
insert(rson, m + 1, r, x, y, v);
else
insert(lson, l, m, x, m, v),
insert(rson, m + 1, r, m + 1, y, v);
up(rt);
}
ll calc(int rt, int l, int r, int x, int y) {
if (x == l && r == y)
return tr[rt];
down(rt, l, r);
int m = mid;
if (y <= m)
return calc(lson, l, m, x, y);
else if (x > m)
return calc(rson, m + 1, r, x, y);
else
return calc(lson, l, m, x, m) + calc(rson, m + 1, r, m + 1, y);
}
void solve(int index) {
memset(tr, 0, sizeof tr);
memset(lz, 0, sizeof lz);
cin >> n >> m;
insert(1, 1, n, 1, n, 1);
while (m--) {
int x, y, t;
cin >> x >> y >> t;
insert(1, 1, n, x, y, t);
}
printf("Case %d: The total value of the hook is %lld.\n", index, calc(1, 1, n, 1, n));
}
int main() {
cin >> _;
for (int i = 1; i <= _; i++)
solve(i);
return 0;
}