BZOJ 2527 [Poi2011]Meteors

发布于 2017-09-12  139 次阅读


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

题意:见原题面。


整体二分的初体验= =

简单的说,流程是这样的:solve(l,r,L,R) 处理 [l,r] 的国家,且它们的答案在 [L,R]。

每次暴力将操作指针跑到 (L+R)/2,看看有哪些国家被满足了,被满足的放到左边,其余放到右边。

实现中有一点小细节:判断国家有没有被满足要 break,不仅优化常数,还防止了爆 long long...

另外这么做的复杂度是可以保证的,YY 下,操作指针不会瞎跳= =,大概会从 mid 跳到 1,再从 mid 跳到 n 这种感觉,可以证明跳的距离不超过 3n

判断每个位置收到了多少陨石可以用树状数组维护差分前缀和,就没了= =写了好久 1A 还是很舒服的

 


一个非常弱的准退役OIER