@[zyh0516_lucky](/user/746930) 您好，莫队复杂度应该是 $O(m\sqrt{n})$，而 ST 为 $O(m\log n)$
by WydnksqhbD_3 @ 2024-04-17 22:25:49
@[WydnksqhbD_3](/user/753481) 所以ST更快，thx
by zyh0516_lucky @ 2024-04-17 22:28:50
@[zyh0516_lucky](/user/746930)
莫队复杂度虽是
$O(m\sqrt{n})$
ST快组是
$O(mlog_2n)$
但如果在特殊的情况下，例如元素<4，或有序度足够，他们两个都一样
by xpg007 @ 2024-04-17 22:40:41
@[xpg007](/user/1024680) thx
by zyh0516_lucky @ 2024-04-17 22:41:33
莫队求 rmq 有点太难写了吧
by yukimianyan @ 2024-04-18 08:43:02
@[WydnksqhbD_3](/user/753481) 一眼 GPT 回复
@[zyh0516_lucky](/user/746930)
显然 st 表更快，单次 $O(1)$，预处理 $O(n \log n)$， 码量就 6 行，完全碾压莫队啊
你是不是在做理想的正方形
by I_AK_CSP_J @ 2024-04-18 08:43:08
不仅要离线询问还要回滚/yun
by yukimianyan @ 2024-04-18 08:43:23
@[I_AK_CSP_J](/user/1080722) 那个人就说了个复杂度，怎么就 GPT 回答了？
~~而且 lz 大概是想团队里的一道题目题解写哪种，别问我怎么知道的~~
by xsmfollower @ 2024-04-18 11:38:53
@[xsmfollower](/user/1308728) 小号你好，lz为什么是对我的称呼
by zyh0516_lucky @ 2024-04-18 12:18:26
@[I_AK_CSP_J](/user/1080722) thx。那题我用单调队列早就A了
by zyh0516_lucky @ 2024-04-18 12:19:03