关于各类分块做法

critnos @ 2020-08-11 12:33:26

by critnos @ 2020-08-11 13:02:06

不过这个理论复杂度很优秀的东西被各种 \log 做法吊着踩（

by Andy_chen @ 2020-08-11 13:38:13

请问咋分块呀？小蒟蒻不会 /kk

by critnos @ 2020-08-11 13:40:16

@Andy_chen 就是说，分块之后维护前缀后缀 \max，块间用奇奇怪怪的东西维护

by Spasmodic @ 2020-08-11 13:40:53

@mcyl35 这有个玄学做法

下面那个

不知道有人看得懂吗

by critnos @ 2020-08-11 13:41:17

然后每次查询就分为三个部分：连续的若干个整块和两个零散块，这个三个东西都已经维护了所以可以 O(1) 查询

by critnos @ 2020-08-11 13:41:53

@happydef 我们机房屏蔽了大多数网站。。您能讲下思路吗QAQ

by Spasmodic @ 2020-08-11 13:42:41

@mcyl35 一杯茶，一包烟，一个块长调一天

by bellmanford @ 2020-08-11 13:44:15

stO 26535 Orz

by critnos @ 2020-08-11 13:44:43

zkw 线段树？

by Spasmodic @ 2020-08-11 13:45:12

https://zhuanlan.zhihu.com/p/79423299

顺便一提，这个是我从skydogli的犇犇里面找到的