劝退一下写ST表的同学们

P1886 滑动窗口 /【模板】单调队列

云浅知处 @ 2020-07-06 02:16:58

此题空间 10^7，ST表的话，那两个二维数组直接爆空间......

当然如果ST表过了，欢迎打脸。

by fzj2007 @ 2020-07-06 11:03:47

@B_1168 ~~看我把正解卡了……~~

by B_1168 @ 2020-07-06 11:07:41

@Immortal_Bird ~~32Mb，两个O(n)数组，不能再多了~~

by B_1168 @ 2020-07-06 11:09:20

@fzj2007 加了臭氧、结构体、fread且自带小常数的单调队列运气好估计能卡到100ms之内，这都要卡就态度留了

by B_1168 @ 2020-07-06 11:09:33

*太毒瘤

by fzj2007 @ 2020-07-06 11:14:28

@B_1168 ……

by B_1168 @ 2020-07-06 11:38:23

@fzj2007 ~~不要问我怎么知道这些卡常方法的（滑稽）~~

by B_1168 @ 2020-07-06 11:40:52

@duyh1114 ~~好像这道题的历史的确比ST表久~~

by critnos @ 2020-07-06 12:45:35

这啊，你能卡分块 ST？

by bovine__kebi @ 2020-07-06 13:15:40

@B_1168 ~~但是实际操作不难啊（~~

by B_1168 @ 2020-07-06 23:06:01

@bovine__kebi ~~写起来毒瘤，而且常数巨大，对非随机数据是可能卡到O(n\sqrt{n})复杂度的，所以真的不如笛卡尔树~~