整段修改刚开始还求前后两值的差,卡了一下发现直接改就行了。
题意和题解: 线段树板子区间修改区间查询,由于本题查一整段所以无需查询操作
代码:
//修改区间为同一个值
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int T, n, m;
struct Node{
int l, r;
int sum, add;
}tr[N << 2];
void pushup(int u) {
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u) {
Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if(root.add) {
left.add = right.add = root.add;
int mid = root.l + root.r >> 1;
left.sum = (mid - root.l + 1) * root.add;
right.sum = (root.r - (mid + 1) + 1) * root.add;
root.add = 0;
}
}
void build(int u, int l, int r) {
tr[u] = {l, r, 1, 0};
if(l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void modify(int u, int l, int r, int x) {
if(tr[u].l >= l && tr[u].r <= r) {
tr[u].sum = (tr[u].r - tr[u].l + 1) * x;
tr[u].add = x;
return ;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1, l, r, x);
if(r > mid) modify(u << 1 | 1, l, r, x);
pushup(u);
}
int main()
{
scanf("%d", &T);
for(int g = 1; g <= T; g++) {
scanf("%d%d", &n, &m);
build(1, 1, n);
while(m--) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
modify(1, x, y, z);
}
printf("Case %d: The total value of the hook is %d.\n", g, tr[1].sum);
}
return 0;
}