保存帖子
发现
索引
热门
陶片放逐
关于
关于莫队复杂度
板块
学术版
楼主
ppip
嘟嘟嘟
当前回复
15
已保存回复
15
发布时间
2022/7/27 19:02
上次更新
2023/10/27 18:07:52
查看原帖
更新帖子
被骇客
银
狼
阻止的越权访问
保存失败
关于莫队复杂度
ppip
嘟嘟嘟
楼主
2022/7/27 19:02
莫队（块长取
n
\sqrt{n}
n
，询问次数为
m
m
m
）右端点转移显然是
O
(
n
n
)
O(n\sqrt{n})
O
(
n
n
)
不提。左端点每次询问最坏转移
O
(
n
)
O(\sqrt{n})
O
(
n
)
次，似乎是
m
n
m\sqrt{n}
m
n
？为啥说总复杂度是
O
(
n
n
+
m
)
O(n\sqrt{n}+m)
O
(
n
n
+
m
)
呢？
有资料说莫队块长取
n
m
\dfrac{n}{\sqrt{m}}
m
n
更优，具体在什么情况呢？
2022/7/27 19:02
加载中...
