竭诚为您提供优质文档/双击可除
poj,线段树模板题
篇一：poj20道线段树汇总
pojpku线段树题目20道汇总+简要算法+分类+难度来源：黑梦楠的日志
难度系数分为从1到5（只对初学者有用对大牛来讲这些题的难度系数都是
0..)http://acm.pku.edu.cn/judgeonline/problemid=1151
atlantis扫描线+离散化+线段树
这是经典的扫描线求矩形面积交很好过没什么陷阱如果头一次接触扫描线那么难度系数大概算3吧如果熟练掌握扫描线难度系数为1 难度系数***
http://acm.pku.edu.cn/judgeonline/problemid=1177picture扫描线+线段树
扫描线求矩形周长的并比求面积并难线段树中的域要多考虑几个部分需要掌握维护线段树存储线段的段数与长
第 1 页 共 21 页
度和经典中的经典题目 难度系数****
http://acm.pku.edu.cn/judgeonline/problemid=1389 areaofsimplepolygons
直接拿1151的代码ac没什么好说的 难度系数***
http://acm.pku.edu.cn/judgeonline/(poj,线段树模板题)problemid=1823
hotelpoj3667的姊妹篇不要看ac率不高但是比3667容易些吧线段树线段的插入删除求线段树中最长的线段长度不错的题目 难度系数***
http://acm.pku.edu.cn/judgeonline/problemid=2104 k-thnumber
线段树维护归并排序树+三次二分查找别以为这题ac率高就容易多数人没用这算法而是水过去的为了练习线段树还是好好做吧...~三次二分挺容易出错的 难度系数*****
http://acm.pku.edu.cn/judgeonline/problemid=2155mat
第 2 页 共 21 页
rix
楼教出的二维线段树..也可以用二维树状数组题目容易理解没有陷阱 难度系数**
http://acm.pku.edu.cn/judgeonline/problemid=2299ultra-quicksort
线段树求逆序数最基础的线段树计数问题没什么好说的..
难度系数*
http://acm.pku.edu.cn/judgeonline/problemid=2352stars
也是线段树计数问题求比当前插入的数小的数的个数简单题 难度系数*
http://acm.pku.edu.cn/judgeonline/problemid=2482 starsinyourwindow
扫描线+离散化+线段树刘汝佳黑书中介绍过算法不过我觉得不是很好看懂题目规定的矩形框高度为h。 比如，遇到一个星星s位置是(xi,yi)，亮度为bi。
第 3 页 共 21 页