求助更优复杂度算法

回复帖子

@return20071007  2020-06-30 18:46 回复

初始为空序列支持末尾追加区间求乘积取模(模数固定)

有一个追加 $\operatorname{O}(1)$ 查询 $\operatorname{O}(\log n)$ 的做法然后

不敢追问,没捣鼓出来(<-我这种DS屑怎么可能捣鼓出来呢)于是来求助了/fad

@return20071007  2020-06-30 19:14 回复 举报

@qwaszx 其实有区别

因为我用的是线段树

lxl爷要是用的什么别的DS的话末尾插入的处理可能和直接给出序列不太一样

@qwaszx 2020-06-30 19:32 回复 举报

感觉了一下好像还是没啥区别...我大概会个 $O((n+q)\log^* n)$ 的东西

@qwaszx 2020-06-30 19:41 回复 举报

@return20071007 先考虑给出序列后查询,按 $\log$ 分块,然后块间建个所谓猫树的东西,块内递归下去,这样树高是 $O(\log^* n)$ 的,末尾追加的话就和那个线段树差不多做

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。