BZOJ 4605 崂山白花蛇草水


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

题意:强制在线带修改询问矩形第 k 大。


考虑在线做法,平面上的修改和矩形询问可以用 KDtree 解决,第 k 大询问是常见的套路,外层套一个权值线段树即可。

(说的容易,你写啊

由于有加点操作,暴力 insert 会导致 KDtree 不够平衡,会 T,于是采用替罪羊式的重构,此处也可以采用插入点数足够大后暴力重构,可过。

结果第二发就 A 了,没卡到 OJ...

另外,struct 和 namespace 在这种大数据结构题中对维护代码整洁性真是太有用了。

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 4605 崂山白花蛇草水


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,