hdoj1698JustaHook【线段树区间更新】

题目大意：有一段链子。初始的时候是铜的（价值为1），n代表有n段（1~n），输入a， b， c三个数分别表示将从a到b的链子的价值改为c， 最后问你经过多次改变之后的总价值。

策略：这道题是简单的线段树的区间更新。

代码：

#include
#include
#define MAXN 100005
#define LC l, m, rt<<1
#define RC m+1, r, rt<<1|1
int sum[MAXN<<2], laz[MAXN<<2];
void PushUp(int rt)
{
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
void PushDown(int rt, int m)
{
if(laz[rt]){
laz[rt<<1] = laz[rt];
laz[rt<<1|1] = laz[rt];
sum[rt<<1] = laz[rt]*(m-(m>>1));
sum[rt<<1|1] = laz[rt]*(m>>1);
laz[rt] = 0;
}
}
void creat(int l, int r, int rt)
{
if(l == r){
sum[rt] = 1;
return;
}
int m = (l+r)>>1;
creat(LC);
creat(RC);
PushUp(rt);
}
void update(int le, int ri, int num, int l, int r, int rt)
{
if(le <= l&&r <= ri){
laz[rt] = num;
sum[rt] = num*(r-l+1);
return;
}
PushDown(rt, r-l+1);
int m = (l+r)>>1;
if(le <= m) update(le, ri, num, LC);
if(ri > m) update(le, ri, num, RC);
PushUp(rt);
}
int main()
{
int t, n, m, v = 1;
scanf("%d", &t);
while(t --){
memset(sum, 0, sizeof(sum));
memset(laz, 0, sizeof(laz));
scanf("%d", &n);
creat(1, n, 1);
scanf("%d", &m);
int a, b, c;
while(m --){
scanf("%d%d%d", &a, &b, &c);
update(a, b, c, 1, n, 1);
}
printf("Case %d: The total value of the hook is %d.\n", v++, sum[1]);//由于是直接求总价值，直接输出sum[1]就能够了
}
return 0;
}

pid=1698

AC by SWS