一本满足的线段树专题 | Winterfell30's Blog
因为连着两场比赛坑了线段树，所以我打算好好补一下线段树，我线段树的代码风格一直是学习HH神�牡模�感觉很简洁，飘逸。
以下题目有些是HH神�牡淖ㄌ饫锩娴模�有些是我在VJ上找的，自我感觉都是些还不错的题目。
因为以前写专题总是一次做完再写要写很久。。。所以这次边做边更。。。
1.单点更新
线段树的单点更新比较简单，比赛中大都是用来配合其他类型题目来使用的（比如DP）。
所以虽然题目都比较简单，但是熟练使用还是挺重要的。
HDOJ 1166 敌兵布阵
单点增减，区间求和。
AC代码链接
HDOJ 1754 I Hate It
单点修改，区间求最值。
AC代码链接
HDOJ 1394 Minimum Inversion Number
先用线段树求一下逆序数，然后把所有情况递推一下找到最大值就行了。
单点修改，区间求和。
AC代码链接
HDOJ 2795 Billboard
求区间最大值，然后减去L，可以直接在query里面update。
单点修改，区间查询。
AC代码链接
POJ 2352 Stars
以前用树状数组AC过，思路相同，线段树的区间从左到右为1~32000，一个一个插入。
单点修改，区间查询。
AC代码链接
2.区间更新
区间更新使用了懒惰标记，不更新到节点使得效率更高。
关于懒惰标记不再赘述，注意在线段树操作的时候总是要PushDown，只有update的时候才需要PushUp。
在query里面的PushDown是将父节点没有传递下去的部分传下去，这里不是更新，是之前懒惰标记的更正。
PushUp是将子节点传给父节点，子节点的值没有变化，所以不需要PushUp。
HDOJ 1698 Just a Hook
屠夫的钩子是铜的，可以把一段钩子变成金的或者银的，问最后总价值是多少。
区间替换，查询直接输出sum[root]就行了。
AC代码链接
POJ 3468 A Simple Problem with Integers
给出一些数，可以把一个区间里面的数都增加一个数，求给出区间的和。
区间增添，区间查询。
AC代码链接
Read full article from 一本满足的线段树专题 | Winterfell30's Blog
No comments:
Post a Comment