HNOI2015 接水果

Source and Judge

HNOI2015 接水果

Record

1h

Analysis

请先思考后再展开

目前见过最难的整体二分了,但也不是很难,可能是我刷题太少

包含这东西,很显然可以化化柿子,然后就是dfs序的一个矩形

问题转化为,求每个点,覆盖它的矩形中,第k大的
整体第k大的查询,就是很套路
二分以后,重点就是check,用小于mid的部分,询问被多少个覆盖掉
那这个暴力搞得话例如cdq、树套树什么的……但都太复杂了没细想
其实,终点在于它是一个矩形,可以扫描线搞

例如说拆成左线段和右线段,然后就变成修改和查询,然后就树状数组询问次数就好了

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/4478.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%