社区讨论

暴力分块的最佳块大小

2025/08/18 12:43P3380【模板】树套树参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

提示：暴力分块的最佳分块大小。

这里说的暴力分块，不是题解那种值域分块，是每块自己排一个序的做法，这样一来总代价：

O( B + \frac nB·\log B )

所以说不完整块和完整块查询不平衡，肯定不能取根号，这玩意好像也不能简单求出来，所以枚举计算了一下 B 在1300~1800左右最优，轻松跑到2.4秒，而取根号（223左右）要跑十秒

共 3 条回复，欢迎继续交流。

正在加载回复...