BZOJ1176:「Balkan2007」Mokia 题解

主要思路

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *