这是一个历史遗留题,今天突然想到了就发了上来

题目是这样的:区间加等比数列,区间求和。(来自 @ )

然后我的思路是:

分块(块长 B1B_1)。散块暴力求和。整块维护和,并且用一个 vector 维护 tag

每当块内 tag 数量达到 B2B_2 时,使用分治+NTT 最后求逆相乘的方式求出所有 tag 对应的 OGFOGF 之和。重构次数为 O(nmB1B2)O({nm \over B_1B_2})

时间复杂度 Θ(mB1+mB2logP+nmB1+nmB1B2(B2log2B2+B1logB1))\Theta(mB_1 + mB_2 \log P + {nm \over B_1} + {nm \over B_1B_2}(B_2 \log^2 B_2 + B_1 \log B_1))nn 为数列长度,mm 为操作数,PP 为模数)。n,mn,m 同阶时取 B1=nlogn,B2=nB_1=\sqrt{n}\log n,B_2=\sqrt{n},则复杂度为 Θ(nn(logn+logP))\Theta(n \sqrt{n}(\log n+\log P))

问一下以上思路是否可行。

2 comments

  • 1