Description

给定序列 $a=(a_1,a_2,\cdots,a_n)$ 和常数 $k$，$q$ 次操作：

• 1 x y：将 $a_x$ 改成 $y$。
• 2 l r：求 $a[l,r]$ 中长度在 $[0,k]$ 之间的最大子段和。

Limitations

$1\le n\le 2\times 10^5$

$1\le q\le 4\times 10^5$

$|a_i|,|y|\le 10^9$

$4\text{s},1\text{GB}$

Solution

将序列分成长为 $k$ 的块，那么答案只可能在块内和块间产生。

块内是平凡的，直接线段树维护即可。

对于块间，维护 $[l,r+k]$ 的答案，设 $A=[l,r],B=[l+k,r+k]$。

考虑合并，答案分为以下情况：

• 左半的答案拼上右半的整段 $A$。
• 右半的答案拼上左半的整段 $B$。
• 左边 $B$ 的一段前缀拼上右边 $A$ 的一段后缀。

将需要的信息用线段树维护即可。

考虑查询，散块直接用上面两棵来求。对于整块内和整块间，我们不能暴力枚举块求 $\max$，于是再开两棵线段树维护 RMQ 即可。

为了减少分类讨论，可以把块间线段树的 $l-1$ 和 $r+1$ 位置临时改成 $-\infty$。

做完了，时间复杂度 $O((n+q)\log n)$。