Gravatar
┭┮﹏┭┮
积分:2914
提交:739 / 1642
稍微卡内存

Gravatar
lihaoze
积分:1314
提交:352 / 742
参考clj大佬论文《区间众数命题报告》,预处理每个块中数的数量,相比《进阶指南》的二分做法效率显著提高(具体来说,同开O2的情况下快了将近1s),时间复杂度从$O((n + m) \sqrt n \log n)$ 优化至 $O((n + m) \sqrt n)$。唯一的缺点就是代码难度剧增(调试起来很痛苦,比如我数组大小是按照 $O(n^{1.5})$ 来的,但是分块大小还是选择的 $O(\sqrt{n \log n})$,导致调试了一下午发现不了问题,包括边界问题也调整了半天)。至于WJMZBMR神犇的论文可以参考这里 Onedrive,很有参考价值

题目 3231 蒲公英
2022-08-24 21:02:59
Gravatar
Hale
积分:2099
提交:510 / 1054
神仙分块,费脑子还费时间