set 应该可以 $O(\log n)-O(\log n)$
by feecle6418 @ 2020-08-07 08:56:49
我想在实现莫队时根号平衡
by 试试事实上吗 @ 2020-08-07 08:58:09
@[试试事实上吗](/user/199750) 分块可以
by Kubic @ 2020-08-07 09:04:34
@[Kubic](/user/119621) 大佬请问怎么分块啊
by 试试事实上吗 @ 2020-08-07 09:06:18
@[试试事实上吗](/user/199750) 开一个值域分块，然后每一个块记录当前块中的最小差，暴力扫根号个块，特判边界也就是要维护一下max，min，但是有个缺点是你没法比较好的达到删除，我想到的删除可能还需要记录前驱后继
by zzqDeco @ 2020-08-07 11:53:22
如果可以直接就用不删除，不然常数会很大
by zzqDeco @ 2020-08-07 11:53:45
@[zzqDeco](/user/62573) 蒟蒻小声提问:怎么O(1)维护块内最小差啊
by disposrestfully @ 2020-08-07 18:50:58
@[disposrestfully](/user/8601) 记录下来吧，你只要考虑更新就好了
by zzqDeco @ 2020-08-07 18:57:34
@[zzqDeco](/user/62573) 我感觉插入一个数的时候好像要查询块内前驱后继？这个能做到O(1)吗？还是说不用查询这个？
by disposrestfully @ 2020-08-07 18:58:55
@[disposrestfully](/user/8601) 就记录吧，我也说了要前驱后继，并且还要maxmin，做到O1当然可以，这个和链表是等价的吧
by zzqDeco @ 2020-08-07 19:14:13