本文主要是介绍pku线段树20题（mark），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
难度系数 分为从1 到 5 （只对初学者有用 对大牛来讲 这些题的难度系数都是0..)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1151
Atlantis 扫描线+离散化+线段树
这是经典的扫描线求矩形面积交 很好过 没什么陷阱 如果头一次接触扫描线 那么难度系数大概算3吧 如果熟练掌握扫描线 难度系数为1
难度系数 ***
http://acm.pku.edu.cn/JudgeOnline/problem?id=1177
Picture 扫描线+线段树
扫描线求矩形周长的并 比求面积并难 线段树中的域要多考虑几个部分 需要掌握维护线段树存储线段的段数与长度和 经典中的经典题目
难度系数 ****
http://acm.pku.edu.cn/JudgeOnline/problem?id=1389
Area of Simple Polygons
直接拿1151的代码AC 没什么好说的
难度系数 ***
http://acm.pku.edu.cn/JudgeOnline/problem?id=1823
Hotel
poj 3667的姊妹篇 不要看AC率不高 但是比3667容易些吧 线段树 线段的插入删除 求线段树中最长的线段长度 不错的题目
难度系数 ***
http://acm.pku.edu.cn/JudgeOnline/problem?id=2104
K-th Number
线段树维护归并排序树+三次二分查找 别以为这题AC率高就容易 多数人没用这算法 而是水过去的 为了练习线段树 还是好好做吧...~ 三次二分挺容易出错的
难度系数 *****
http://acm.pku.edu.cn/JudgeOnline/problem?id=2155
Matrix
楼教出的二维线段树..也可以用二维树状数组 题目容易理解 没有陷阱
难度系数 **
http://acm.pku.edu.cn/JudgeOnline/problem?id=2299
Ultra-QuickSort
线段树求逆序数 最基础的线段树计数问题 没什么好说的..
难度系数 *
http://acm.pku.edu.cn/JudgeOnline/problem?id=2352
Stars
也是线段树计数问题 求比当前插入的数小的数的个数 简单题
难度系数 *
http://acm.pku.edu.cn/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--
经典中的经典题 题目描述还是感人的故事
难度系数 *****
http://acm.pku.edu.cn/JudgeOnline/problem?id=2528
Mayor's posters
了解线段树的估计都做过这题 太典型了 线段染色问题 各种解题报告一大堆
我想说的是注意离散化的方法 不要以为AC了的程序就是完全正确 详情可以看这题的discuss
难度系数 **
http://acm.pku.edu.cn/JudgeOnline/problem?id=2761
Feed the dogs
据说wind养了100000只狗 题目要求和2104基本一样 但是2104的经典算法在这里不适用
一定要注意"Hence any feeding inteval will not contain another completely, though the intervals may intersect with each other. "这句话 为什么 自己要仔细琢磨啊
做这题至少要会用线段树求第k小数
难度系数 ***
http://acm.pku.edu.cn/JudgeOnline/problem?id=2777
Count Color
线段染色问题 很好做 解题报告也一大堆 但希望自己敲敲
难度系数 **
http://acm.pku.edu.cn/JudgeOnline/problem?id=2823
Sliding Window
线段树求RMQ问题 经典的问题 貌似这题的时限挺有意思 算法没啥好说的..
难度系数 **
http://acm.pku.edu.cn/JudgeOnline/problem?id=2828
Buy Tickets
朱泽园出的题 线段树计数 从队伍后往前做 其实没啥好说的...
难度系数 ***
http://acm.pku.edu.cn/JudgeOnline/problem?id=2886
Who Gets the Most Candies?
NB经典题啊 约瑟夫环的升级版本 绝对要掌握的题目 用线段树解约瑟夫环问题
网络预赛就有个这样子的题 不过我当时不会 唉...这题比当时网络预赛难 容易出错
难度系数 ****
http://acm.pku.edu.cn/JudgeOnline/problem?id=3264
Balanced Lineup
线段树求RMQ问题 没什么好说的...
难度系数 **
http://acm.pku.edu.cn/JudgeOnline/problem?id=3277
City Horizon
线段树求和 线段插入等 基础题 不过USACO的标程挺NB的 用set+pair构造线段树
有时间一定学学啊 其实这就是说红黑树添加一个线段域也就成了线段树了..算导上有讲解
难度系数 **
http://acm.pku.edu.cn/JudgeOnline/problem?id=3468
A Simple Problem with Integers
线段树求和...不说了
难度系数 *
http://acm.pku.edu.cn/JudgeOnline/problem?id=3667
Hotel
NB题中的NB题 真正理解了这题 就真正理解了线段树 解题报告有很多 这题涉及了 线段合并 线段插入删除 求线段树上最大连续线段长度 线段求和等 一定要做的题目
难度系数 *****
http://acm.pku.edu.cn/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道线段树题目 欢迎大家分享与补充 指正错误 转帖请注明出处 数据结构是门艺术 算法也是门艺术 线段树是门艺术中的艺术
这篇关于pku线段树20题（mark）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
