求助更优复杂度算法

回复帖子

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

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

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

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

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

@LanrTabe 整一棵线段树,末尾追加的时候从下往上构建出每一个插满了的节点,每个节点只会被插一次所以末尾插入复杂度相当于建树复杂度

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



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