bzoj 5168: [HAOI2014]贴海报 & 5029: 贴小广告 离散化+扫描线+set

题目链接1:https://www.lydsy.com/JudgeOnline/problem.php?id=5168

题目链接2:https://www.lydsy.com/JudgeOnline/problem.php?id=5029


bzoj喜加二!

一眼看上去就很水,但是最开始想的是线段树,由于空间不够,也懒得写线段树,所以又思考一番,发现其实很水

将每个海报拆成两个点,记录下id,代表它是第几个被贴上去的

按照下标从小到大排个序

然后每次一口气把当前下标上的操作全都处理完,再统计下当前的答案

当前的答案就是目前还贴着的海报当中id最大的那个,这个可以用一个set来维护

注意:需要把右端点的值+1,因为是闭区间

 

bzoj 5168: [HAOI2014]贴海报 & 5029: 贴小广告 离散化+扫描线+set》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注