题解：P13982 数列分块入门 7

Jadonyzx · 2025-09-06 14:03:44 · 题解

分块。

考虑如何更新。

对于散块，直接暴力更新，这部分的复杂度是 O(\sqrt n) 的。

对于整块，我们维护两个懒标记，具体地，我们的懒标记维护一个一次函数 y=kx+b。

对于乘法，y=(kx+b)\times t=k\times t+b \times t。

两个标记都乘上乘的倍数。

对于加法，y=kx+b+t=kx+b+t。

加法标记加上 t 即可。

初始时 k=1，b=0。

注意，这里暴力更新时为了防止查询的时候出现问题，我们在暴力更新的时候要清空所在块的懒标记。

查询相信看懂上面的也就会了，直接将 x 带入 y=kx+b 即可。