相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4237
神犇题解:http://blog.csdn.net/lqybzx/article/details/51784992
解题报告
这题一年前就考过,当时连$O(n^2)$的容斥都不会 QwQ
当时知道std是分治的时候,眼珠子都快掉出来了
现在来看的话,因为做过BZOJ 4456,所以还是勉强能想出来?
考虑对y轴分治,这样每一次就只需要考虑跨过分治线的所有矩形了
这样的话,我们枚举合法矩形的右上端点,合法的左下端点的纵坐标就是单调下降的了
于是维护一个单调栈什么的就可以啦!
Do you mind if I quote a couple of your articles as long as I provide credit and sources back to your blog? My blog is in the very same niche as yours and my visitors would really benefit from a lot of the information you provide here. Please let me know if this ok with you. Many thanks!
Some really nice and useful information on this site, besides I believe the style and design has great features.