劝退一下写ST表的同学们

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

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

其实看看P3943多少80 TLE的，有一个算一个都是分块ST的（捂脸

by bovine__kebi @ 2020-07-07 08:00:15

@B_1168 比如我（(((

但是如果你卡我这个，我就可以调小块长让你没法卡啊(

by B_1168 @ 2020-07-07 10:39:28

@bovine__kebi 同是天下被卡人（捂脸）

不过嘛，分块ST法貌似在非随机复杂度下的最劣值应该是O(n\log{\sqrt{n}})，但考虑到其巨大的常数，需要千万级别的数据才能和火车头+fread+自带小常数的zkw拉开差距……

欢迎参考：zkw卡P3793尝试，n,m=10^7的点卡了个4.70s，往上一律TLE

by Suuon_Kanderu @ 2020-07-23 15:20:34

为什么要用ST表啊，单调队列又好理解又好写……

by Little09 @ 2020-07-29 10:27:23

单调队列真香啊

by 今天也要开心a @ 2020-07-31 09:59:39

@云浅知处 您应该是没有看到这个帖子 戳这里

by Xiaonanu @ 2023-11-18 15:30:49

哇！管理员