分享
pojpku线段树题目20道汇总+简要算法+分类+难度来源： 黑梦楠的日志
这两天做了几个线段树的题目与大家分享欢迎补充
难度系数分为从1 到 5 （只对初学者有用对大牛来讲这些题的难度系数都是0..)
acm./JudgeOnline/problem?id=1151
Atlantis 扫描线+离散化+线段树
这是经典的扫描线求矩形面积交很好过没什么陷阱如果头一次接触扫描线那么难度系数大概算3吧如果熟练掌握扫描线难度系数为1
难度系数 ***
acm./JudgeOnline/problem?id=1177
Picture 扫描线+线段树
扫描线求矩形周长的并比求面积并难线段树中的域要多考虑几个部分需要掌握维护线段树存储线段的段数与长度和经典中的经典题目
难度系数 ****
acm./JudgeOnline/problem?id=1389
Area of Simple Polygons
直接拿1151的代码AC 没什么好说的
难度系数 ***
acm./JudgeOnline/problem?id=1823
Hotel
poj 3667的姊妹篇不要看AC率不高但是比3667容易些吧线段树线段的插入删除求线段树中最长的线段长度不错的题目
难度系数 ***
acm./JudgeOnline/problem?id=2104
K-th Number
线段树维护归并排序树+三次二分查找别以为这题AC率高就容易多数人没用这算法而是水过去的为了练习线段树还是好好做吧...~ 三次二分挺容易出错的
难度系数 *****
acm./JudgeOnline/problem?id=2155
Matrix
楼教出的二维线段树..也可以用二维树状数组题目容易理解没有陷阱
难度系数 **
acm./JudgeOnline/problem?id=2299
Ultra-QuickSort
线段树求逆序数最基础的线段树计数问题没什么好说的..
难度系数 *
acm./JudgeOnline/problem?id=2352
Stars
也是线段树计数问题求比当前插入的数小的数的个数简单题
难度系数 *
acm./JudgeOnline/problem?id=2482
Stars in Your Window
扫描线+离散化+线段树刘汝佳黑书中介绍过算法不过我觉得不是很好看懂
题目规定的矩形框高度为h。
比如，遇到一个星星S位置是(xi,yi)，亮度为bi。
那么线段树区间[yi,yi+h)增加bi。
线段树的每个区间节点保存了该区间内的最大值。
可以从贡献的角度来理解，星星S对区间[yi,yi+h)的贡献度为bi。
扫描线在x轴方向标记进出的线段和求矩形面积并似的进的话cover++ 出的话cover--
经典中的经典题题目描述还是感人的故事
难度系数 *****
acm./JudgeOnline/problem?id=2528
Mayor's posters
了解线段树的估计都做过这题太典型了线段染色问题各种解题报告一大堆
我想说的是注意离散化的方法不要以为AC了的程序就是完全正确详情可以看这题的discuss
难度系数 **
acm./JudgeOnline/problem?id=2761
Feed the dogs
据说wind养了100000只狗题目要求和2104基本一样但是2104的经典算法在这里不适用
一定要注意"Hence any feeding inteval will not contain another completely, though the intervals may interct with each other. "这句话为什么自己要仔细琢磨啊
做这题至少要会用线段树求第k小数
难度系数 ***
acm./JudgeOnline/problem?id=2777
Count Color
线段染色问题很好做解题报告也一大堆但希望自己敲敲
难度系数 **
acm./JudgeOnline/problem?id=2823
Sliding Window
线段树求RMQ问题经典的问题貌似这题的时限挺有意思算法没啥好说的..
难度系数 **
acm./JudgeOnline/problem?id=2828
Buy Tickets
朱泽园出的题线段树计数从队伍后往前做其实没啥好说的...
难度系数 ***
acm./JudgeOnline/problem?id=2886
Who Gets the Most Candies?
NB经典题啊约瑟夫环的升级版本绝对要掌握的题目用线段树解约瑟夫环问题
网络预赛就有个这样子的题不过我当时不会唉...这题比当时网络预赛难容易出错
难度系数 ****
acm./JudgeOnline/problem?id=3264
Balanced Lineup
线段树求RMQ问题没什么好说的...
难度系数 **
acm./JudgeOnline/problem?id=3277
City Horizon
线段树求和线段插入等基础题不过USACO的标程挺NB的用t+pair构造线段树
有时间一定学学啊其实这就是说红黑树添加一个线段域也就成了线段树了..算导上有讲解
难度系数 **
acm./JudgeOnline/problem?id=3468
A Simple Problem with Integers
线段树求和...不说了
难度系数 *
acm./JudgeOnline/problem?id=3667
Hotel
NB题中的NB题真正理解了这题就真正理解了线段树解题报告有很多这题涉及了线段合并线段插入删除求线段树上最大连续线段长度线段求和等一定要做的题目
难度系数 *****
acm./JudgeOnline/problem?id=3695
Rectangles
线段树求矩形面积并可以用融斥原理说实话...这题挺猥琐的算法没难度不过如果搞不好的话非常容易超时下面是我在discuss中留的言:
1 TLE的话应该是没离散化这题必须离散化原以为最长1000的线段可以不离散化可是最多有20个矩形那最多就有40个线段 100000*log40和100000*log1000时间肯定是不一样...
2 只建立一次线段树..不要问一次建一次因为加入的线段过后肯定会被删除
3 最好只开始的时候对线段排次序然后开个mark[]数组记录哪几个矩形的线段是此次询问要选的不要每次询问都对线段排序..
4 别用G++交...G++比C++平均慢了500MS 这题就卡了那么点时间
5 前边的优化如果都做了的话..应该就过了
上边是poj的20道线段树题目欢迎大家分享与补充 指正错误转帖请注明出处数据结构是门艺术算法也是门艺术线段树是门艺术中的艺术
