定长分块

· · 算法·理论

P9877 [EC Final 2021] Vacation

给定常数 C。维护长为 n 的序列 a_i,支持 q 次操作:

  • 给定 i,x,令 a_i \gets x。
  • 给定 l,r,求 \max\left(0,\max \limits_{[x,y] \subseteq [l,r] \land y-x+1 \le C} \sum \limits_{i=x}^y a_i\right)。

:::::success[题解]

我们使用定长分块的技巧,将序列每 C 个元素分到一块,则答案区间只能在同块内,或者在相邻两块内。

对于同块的情形容易处理,对每块开线段树支持单点修改,区间最大子段和,半群信息的构造是经典的。查询时散块直接查,整块查询需要对块序列建线段树,维护区间 \max 快速求值。

现在讨论相邻块的处理方法。类似二区间合并地,设前块的后缀和为 a_i,后块的前缀和为 b_i,则答案可以表示为 \max \limits_{i+j \le C} (a_i+b_j)。

转 i-j 二维平面分析,则每个点 (i,j) 带权 a_i+b_j,查询是对 i+j \le C 这个直角三角形区域数点。

对于左下开口的 2-side 矩形,其对应 i \le x \land j \le y 的限制,i,j 独立,求解是容易的。这启发我们从直角三角形中划出一个矩形,分成矩形和两个小直角三角形进行维护,而小的三角形可以继续递归:

我们用线段树来维护这个分治结构。具体地,对于线段树区间 [l,r],我们令其表示 i \in [l,r] \land j \in [C-r,C-l] 的直角三角形。对 [l,r] 做 pushup 时,小三角形可以作为左右儿子递归,而矩形区域内 i,j 独立,分别维护 a_i 和 b_j 的 \max 即可。对三个区域的答案求 \max 即为当前节点的答案。

由于 a,b 是前后缀和,故修改是对 a,b 的区间加减。我们维护的信息只有 \max a, \max b 和区域内答案,则修改是容易用标记解决的。

整块的跨块贡献直接提取根节点答案即可。对于散块,有可能出现区间包含块边界且截断整块的情况,此时的限制形如 i \le x \land j \le y \land i+j \le C,可能是矩形 / 梯形 / 五边形区域。我们都可以划分为若干矩形和若干三角形得到答案:

这样整个问题得到解决。复杂度 O(q \log n)。

:::::

P17579 [JAG 2026 Summer Camp #3] Noise Cancelling

称序列 x_1 \sim x_{2m} 是优美的,当且仅当 \forall i \in [1,m], x_i+x_{i+m}=0。给定长为 n 的序列 a_i,求优美的子数组 a[l:r] 数目。

:::::success[题解]

枚举 m=k 并将序列以 k 为块长定长分块,则优美区间恰好跨越两个关键点。关键点数目是调和级数的 O(n \log n)。

考察相邻关键点 x,y。设优美区间的起点 l=x-d,我们要求 x-d \sim x-d+k-1 和 y-d \sim y-d+k-1 相等。这里的相等定义为 \forall i, a_i=-b_i。

设 u=\text{lcp}(x,y) 和 v=\text{lcs}(x-1,y-1)。左边需要匹配 d 个元素,右边需要匹配 k-d 个元素,可列得约束:

解得 l 的范围是一段区间,统计贡献即可。

对于 u 的求解,可以将 a_i 取反拼到后面跑 SA,查询 v 只要取反串 SA。

复杂度 O(n \log n)。代码。

:::::