BZOJ 4605 崂山白花蛇草水

发布于 2017-11-18  209 次阅读


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

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


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

(说的容易,你写啊

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

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

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

 


一个非常弱的准退役OIER