bzoj 2501: [usaco2010 Oct]Soda Machine 离散化

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2501


一开始觉得这题不是线段树随便搞,后来看了眼数据范围就放弃了

 

先离散化,记录一下是左端点还是右端点

然后按照下标从小到大排序,如果下标相同左端点在前 (因为边界也算覆盖)

然后对排序完的点集从小到大扫,now记录目前被几个线段覆盖,碰到左端点就+1,碰到右端点就-1,ans取最大的now就行

 

发表评论