BZOJ1176:[Balkan2007]Mokia 题解

主要思路

这道题的\(w\)很大,且要求出二维和。一种可行的办法就的是嵌套数据结构,第一想法是树状数组套线段树动态开点,时间复杂度为\(O(log^2 m)\)。但是空间依旧很大,可以发现线段树空间庞大,可以考虑替换为平衡树,空间极大减小,且时间复杂度不变。

进一步优化可以考虑对下标进行哈希。

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注