关于一些好像以前没人用的卡常技巧

P3793 由乃救爷爷

JRzyh @ 2021-03-17 21:15:55

1.

先预处理块内前后缀再初始化分块数组。

初始化复杂度 O(n)\rightarrow O(\sqrt{n})

2.

再同一块内有一个特别的搞法：

设 pre_x 是前缀最值， las_x 是后缀最值

若 pre_{l-1}\neq pre_{r} 最值是 pre_r

若 las_{r+1}\neq las_l 最值是 las_{l}

误喷

by _5011_ @ 2021-03-17 21:21:50

感觉第二个用处不会很大，毕竟期望只有1个询问落到同一块里面（

by _5011_ @ 2021-03-17 21:25:34

第一个并没有看懂是怎么做到低于 O(n) 预处理的。。。你不是至少要弄出 O(n) 个数组的值吗。。。

by _5011_ @ 2021-03-17 21:26:48

*O(n) 个值

by JS_TZ_ZHR @ 2021-03-17 21:37:23

@w33z8kqrqk8zzzх33 是 \frac{m}{\sqrt{n}} 罢。

by critnos @ 2021-03-17 21:51:00

我以前好像分析过第二个优化，效果是可以优化掉 \dfrac 1 3 的暴力计算

by critnos @ 2021-03-18 13:20:51

等下子，好像不是

by JRzyh @ 2021-03-21 09:39:50

@mcyl35 效果是优化掉块间最值不在区间内的情况，但不知道是多少

by critnos @ 2021-03-21 13:29:45

@Zhaoyuhang2008 不是块间最值在区间内的情况吗

by critnos @ 2021-03-21 13:31:04

等下，是说整块的最值在 [l,r] 内吗

by JRzyh @ 2021-03-21 13:39:57

@mcyl35 刚才naive了

区间内最值 <pre_{l-1} 且 <las_{r+1}

|