劝退一下写ST表的同学们

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

by 一扶苏一 @ 2020-07-06 03:08:00

@云浅知处 询问是定长，滚动数组不就可以解决空间问题了。

不能 ST 是因为时间复杂度过不去吧

by B_1168 @ 2020-07-06 04:51:46

@一扶苏一 其实如果有卡常技巧的话，甚至连分块都过得去，所以感觉上ST表更大的困难是空间

by B_1168 @ 2020-07-06 04:52:25

分块+O2卡过记录

by B_1168 @ 2020-07-06 05:00:04

ST表其实也能过，看这里

by B_1168 @ 2020-07-06 05:08:08

其实125Mb是开得下2.5\times10^7的整型数组的，10^6\times\log_{2}10^6其实80多mb就可以了

by Yukinoshita_Yukino @ 2020-07-06 06:40:28

多一个log

by zhoukangyang @ 2020-07-06 07:00:01

所以应该加强数据

by twelveZ @ 2020-07-06 07:16:03

这题线段树甚至也能过

by yummy @ 2020-07-06 07:45:40

@zhoukangyang 想啥呢，至今快排板子题不还是能sort水过去吗

by yummy @ 2020-07-06 07:46:21

加强版平衡树不还能用什么WBLT，压缩Trie等等水过去吗