关于莫队块长的疑惑

P4074 [WC2013] 糖果公园

cjwdyzxfblzs @ 2023-06-29 08:54:28

什么情况下使用 n^{\frac{2}{3}} 和 n^{\frac{3}{4}} 好啊？有时候第一种快，有时候第二种快。真的不理解了，到底哪一个是有复杂度保证的呀？？？？

by ღꦿ࿐ @ 2023-06-29 08:57:22

带修莫队时 n^{2/3} 有保障。

有时候取大点会更快。

by yllcm @ 2023-06-29 09:05:49

莫队不是写完之后枚举块长选一个跑得快的吗（

by Johnsonloy @ 2023-06-29 09:11:00

（根号平衡一下

by Johnsonloy @ 2023-06-29 09:11:44

看你的查询修改操作的复杂度来取一个合适的块长（当然如果你一直卡不过去可以试一试奇奇怪怪的常数块长有时候会有奇效）

by too_simple @ 2023-06-29 09:34:24

@sjzez__chess 手算复杂度然后解个式子不就行了吗？

by bingxin @ 2023-06-29 18:21:52

|