hdoj 1698 Just a Hook 【线段树 区间更新】

本文主要是介绍hdoj 1698 Just a Hook 【线段树 区间更新】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

代码：

#include<stdio.h>
#include<string.h>
#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;
}

题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1698

AC by SWS

这篇关于hdoj 1698 Just a Hook 【线段树 区间更新】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---