[ABC256F] Cumulative Cumulative Cumulative Sum Solution

更好的阅读体验戳此进入

题面

给定序列 An,定义 Bi=j=1jAj,Ci=j=1iBj,Di=j=1iCj。存在两种操作:

1 x vAxv

2 x:查询 Dxmod998244353

Solution

就是维护一个高维前缀和,也是经典套路,无脑推式子:

Aa1a2a3ai
Ba1a1+a2a1+a2+a3a1+a2++ai
Ca12a1+a23a1+2a2+a3ia1+(i1)a2++ai
Da13a1+a26a1+3a2+a3(1+2++i)a1+(1+2++(i1))a2++ai

于是可以将 Dx 通过等差数列求和表示为:

Dx=i=1x12(1+x(i1))×(x(i1))ai

然后我们可以考虑将 (1+x(i1))×(x(i1))ai 化简,似乎就是尽量将与询问有关的 x 和前缀和抽离开,这样才可以便于用数据结构维护。即:

(1+x(i1))×(x(i1))ai=(xi+2)×(xi+1)ai=(x2ix+2xix+i22i+xi+2)ai=(x22ix+3x+i23i+2)ai=(x2+3x+2)ai2x(iai)+(i23i)ai

此时我们发现,对于每次询问 x 已知,只需要用数据结构维护 aiiai(i23i)ai 的前缀和即可 O(logn) 查询,并且支持单点修改。记得查询之后乘个 2 的逆元。最终复杂度 O((n+q)logn),可以通过。

Code

UPD

update-2022_12_08 初稿