序列分治学习笔记（基本完成）

· · 个人记录

cnblogs

0x01 前言

序列分治作为一种常见的解决序列问题的算法，有着许许多多的广泛应用。下至普及，上至 NOI，都能看见它的身影。

今年 S 组第一轮完善程序 T2 就考了序列分治，虽然对于那个问题来说分治并不是最优解，但是笔者从中学到了一种序列分治的写法。这也是本文的灵感来源。

本文主要介绍较为基础的序列分治，适合初学者使用。因为笔者也是初学者。

附题单

0x02 算法流程

序列分治通常用于解决⌈子区间贡献⌋一类问题，其基本思想是，假设要计算 [L,R] 范围内的子区间 [l,r] 的贡献，找到区间中点 mid=\dfrac{L+R}{2}，将子区间分为三类：

考虑一个递归的过程，先递归计算 [L,mid] 和 [mid+1,R] 的贡献，再计算第三种，即跨过中点的子区间的贡献。

边界：当 L=R 时，可以直接计算贡献，并返回。我们发现这个分治的结构和线段树十分相似。

时间复杂度的计算通常使用主定理，但是笔者主定理学的很烂，所以喜欢画递归树分析。

不妨通过一道经典的例题来理解这个过程：

SP32079 ADAGF - Ada and Greenflies

  • 给出一个序列 a_1\sim a_n，求：
\sum_{l=1}^n\sum_{r=l}^n \gcd_{i=l}^ra_i

考虑对序列进行分治。设当前分治区间为 [L,R]，中点 mid=\left\lfloor\dfrac{L+R}{2}\right\rfloor。考虑如何计算跨过中点的贡献。

注意到固定右端点 r 后，区间的 \gcd 只会有 \mathcal{O}(\log|V|) 种。因为当左端点左移 1 步时，\gcd 要么不变，要么至少除以 \boldsymbol{2}。

一个跨过中点的区间一定是个左半区间的后缀拼上一个右半区间的前缀。因此考虑预处理左半区间所有后缀以及右半区间所有前缀的 \gcd 的出现次数，使用 __gnu_pbds::gp_hash_table 维护 cl,cr 两个桶。

最后枚举左半区间后缀的 gl，右半区间前缀的 gr，根据乘法原理，贡献为 \gcd(gl,gr)\cdot cl_{gl}\cdot cr_{gr}。

时间复杂度可以这么计算：

  • 设当前分治区间长度为 N。

  • 求左半区间后缀、右半区间前缀的 \gcd 时，\gcd 只变化 \mathcal{O}(\log |V|) 次，这 \mathcal{O}(\log |V|) 次辗转相除的时间复杂度为 \mathcal{O}(\log^2|V|)。而剩下 \mathcal{O}(N) 次 \gcd 不变的时候，根据辗转相除的具体实现容易得知，这些时候求 \gcd 的时间复杂度为 \mathcal{O}(1)。

  • __gnu_pbds::gp_hash_table 的时间复杂度为 \mathcal{O}(1)，枚举左半区间后缀、右半区间前缀的 \gcd 的时间复杂度为 \mathcal{O}(\log^2|V|)。

  • 容易发现瓶颈在于求 \gcd，当前分治区间的时间复杂度为 \mathcal{O}(N)。

  • 根据主定理容易得知整个算法的时间复杂度 T(n)=2\cdot T\left(\dfrac{n}{2}\right)+\mathcal{O}(n)=\mathcal{O}(n\log n)。

  • 用另一种方式分析，分治一共会进行 \log n 层，每一层的总时间复杂度为 \mathcal{O}(\sum N)，容易发现对于任意一层 \sum N=n，因此时间复杂度为 \mathcal{O}(n\log n)。

空间复杂度为 \mathcal{O}(n)。

提交记录 代码

再来看一道例题：

CF817D Imbalanced Array

双倍经验：SP10622。

三倍经验（弱化版）：AGC005B。

  • 给出长度为 n 的序列 a_1\sim a_n，求：
\sum_{l=1}^n\sum_{r=l}^n\left(\max_{i=l}^ra_i-\min_{i=l}^ra_i\right)

这个问题就是今年 S1 完善程序 T2。它给出了一种分治求解⌈最值贡献/限制⌋的方法。

不妨将式子拆开：

\sum_{l=1}^n\sum_{r=l}^n\left(\max_{i=l}^ra_i-\min_{i=l}^ra_i\right)=\sum_{l=1}^n\sum_{r=l}^n\max_{i=l}^ra_i-\sum_{l=1}^n\sum_{r=l}^n\min_{i=l}^ra_i

两个式子的计算是类似的，这里以最大值为例。

设当前分治区间为 [L,R]，中点 mid=\left\lfloor\dfrac{L+R}{2}\right\rfloor。考虑如何计算跨过中点的贡献。

考虑枚举左端点，求出以 i 为左端点、跨过 mid 的区间的总贡献，那么就是 [i,mid+1],[i,mid+2],\dots,[i,r] 这些区间。

维护一个前缀最大值数组 pre_x=\max\limits_{u=mid+1}^x a_u，再对 pre_x 维护前缀和 sum_x=\sum\limits_{u=mid+1}^x pre_u 。

考虑从右往左枚举左端点 i，设右端点为 j，再记一个 mx=\max\limits_{u=i}^{mid} a_u。不难发现可以找到一个分界点 \boldsymbol k 使得当 \boldsymbol{j\in (mid,k)} 时，区间 \boldsymbol{[i,j]} 的最大值为 \boldsymbol{mx}；当 \boldsymbol{j\in[k,r]} 时，区间 \boldsymbol{[i,j]} 的最大值为 \boldsymbol{pre_j}。且随着 \boldsymbol{i} 的减小，\boldsymbol k 单调不降。

那么对于 (mid,k) 的区间，贡献为 (k-1-mid)\cdot mx；对于 [k,r] 的区间贡献为 \sum\limits_{u=k}^r pre_u=sum_r-sum_{k-1}。

边界：当 L=R 时，贡献为 a_L。最小值类似利用单调性做就行了。

时间复杂度为 \mathcal{O}(n\log n)，空间复杂度为 \mathcal{O}(n)。

提交记录（含代码）

0x03 习题

Ⅰ - JOISC2014H JOIOJI

  • 给出一个长度为 n 的字符串，仅由 \texttt{J,O,I} 三种字母组成，求一个最长的子串，使得其中三种字母出现次数相等。

这题扫描线严格优于分治。

双倍经验（弱化版）：CF873B Balanced Substring。

考虑分治，设当前的区间为 [l,r]，中点为 mid。枚举右端点 j，考虑怎样的左端点 i 能够与之组合。

设 u_j=\sum\limits_{k=mid+1}^j[s_k=\texttt{J}]-\sum\limits_{k=mid+1}^j[s_k=\texttt{O}]，v_j=\sum\limits_{k=mid+1}^j[s_k=\texttt{O}]-\sum\limits_{k=mid+1}^j[s_k=\texttt{I}]，a_i=\sum\limits_{k=i}^{mid}[s_k=\texttt{J}]-\sum\limits_{k=i}^{mid}[s_k=\texttt{O}]，b_i=\sum\limits_{k=i}^{mid}[s_k=\texttt{O}]-\sum\limits_{k=i}^{mid}[s_k=\texttt{I}]。

根据题意得知区间满足的条件为：

\sum\limits_{k=i}^j[s_k=\texttt{J}]=\sum\limits_{k=i}^j[s_k=\texttt{O}]=\sum\limits_{k=i}^j[s_k=\texttt{I}]

整理得 a_i+u_j=0，b_i+v_j=0。

于是在左半区间用 map 维护每一个二元组 (a_i,b_i) 出现的最左位置（因为可能有相同的，而且要使得区间最长）。对于右半区间的 j，用 (-u_j,-v_j) 对应的位置与之匹配。

时间复杂度为 \mathcal{O}(n\log^2 n)，空间复杂度为 \mathcal{O}(n)。

提交记录（含代码）

Ⅱ - CF549F Yura and Developers

  • 给定数组 a_1\sim a_n 和常数 k，求有多少个区间 [l,r]，满足:

考虑分治。设当前分治区间左端点为 l，右端点为 r，中点为 mid，考虑如何计算跨过中点的贡献。

首先对于右半区间，维护 pre_p=\max\limits_{u=mid+1}^p a_u，sum_p=\left(\sum\limits_{v=mid+1}^pa_v\right)\bmod k，dif_p=(sum_p-pre_p)\bmod k，即以 mid+1 为起点的前缀最大值、模 k 意义下的前缀和以及它们的差对 k 取模的值。

从右往左扫描跨过中点的区间的左端点 i，记 suf=\max\limits_{v=i}^{mid}a_v，s=\left(\sum\limits_{u=i}^{mid} a_u\right)\bmod k，我们要找到一个位置 j，使得：

\max\limits_{u=mid+1}^{j-1} a_u\le suf\, \land \,\forall \,w\in[j,r],\max\limits_{u=mid+1}^w a_u> suf

说白了就是右端点取在 j 及其左边区间最大值位于 mid 及其左边，右端点取在 j 右边区间最大值位于 mid 右边。不难发现随着 \boldsymbol i 递减，\boldsymbol j 不降。

分别计算以 j 为界的两部分的贡献，对于 j 及其左边，要找到这样的右端点 x，使得 (s+sum_x-suf)\bmod k=0，移项得 sum_x=(k-s+suf)\bmod k；对于 j 右边，要找到这样的右端点 y，使得 (s+dif_y)\bmod k=0，移项得 dif_y=(k-s)\bmod k。

问题变成求 (mid,j) 中有多少 sum 值为 (k-s+suf)\bmod k，[j,r] 中有多少 dif 值为 (k-s)\bmod k。

考虑维护 b1,b2 两个桶，分别表示扫到当前的 j 时 [j,r] 中 dif 在每种值各出现了几次和 (mid,j) 中 sum 在每种值各出现了几次。j 增加到 j+1 时，相当于 (mid,j) 比原来多包含了一个 j 位置，将 b2_{{sum_{j}}} 增加 1；[j,r] 比原来少包含了一个 j 位置，将 b1_{dif_{j}} 减去 1。

这么一来，左端点 i 的贡献为 b2_{(k-s+suf)\bmod k}+b1_{(k-s)\bmod k}，注意边界、负数取模以及清空。

时间复杂度为 \mathcal{O}(n\log n)，空间复杂度为 \mathcal{O}(n+k)。

提交记录（含代码）

Ⅲ - ABC282Ex Min + Sum

  • 给出两个长为 n 的序列 a,b 和常数 S，求有多少个区间 [l,r]\,(1\le l\le r\le n)，满足：

    \min\limits_{i=l}^r a_i+\sum_{j=l}^rb_j\le S

考虑分治。设当前分治区间为 [l,r]，分治中点 mid=\left\lfloor\dfrac{l+r}{2}\right\rfloor。

考虑如何统计跨过中点的区间个数。枚举左端点 i，同时记录 s=\sum\limits_{x=i}^{mid}b_x 和 minn=\min\limits_{y=i}^{mid} a_y。求出有多少个合法的右端点 j。

对于 (mid,r] 这部分区间的所有 j，预处理 sum_j=\sum\limits_{u=mid+1}^j b_u，pre_j=\min\limits_{v=mid+1}^j a_v。

把右端点 j 分成两种，分别统计：

考虑从右往左枚举左端点 i，不难发现可以找到一个分界点 \boldsymbol k 使得当 \boldsymbol{j\in (mid,k)} 时，区间满足第一种情况；当 \boldsymbol{j\in[k,r]} 时，区间满足第二种情况。且随着 \boldsymbol{i} 的减小，\boldsymbol k 单调不降。

使用平衡树 t_1,t_2 分别维护 (mid,k) 中 sum_j 的权值集合和 [k,r] 中 sum_j+pre_j 的权值集合。分界点 k 右移时（接下来的 k 是右移前的 k），在 t_1 中插入 sum_k，在 t_2 中删除 sum_k+pre_k。可以完成⌈查询集合内有多少数不超过某个定值⌋这个操作。

有人可能会说平衡树小题大做，但是 __gnu_pbds::tree 真的很方便。

时间复杂度为 \mathcal{O}(n\log^2 n)，空间复杂度为 \mathcal{O}(n)。

提交记录（含代码）

Ⅳ - CF1156E Special Segments of Permutation

  • 给定一个长度为 n 的排列 p_1\sim p_n，求有多少对 (l,r)，满足：

    • l\le r
    • p_l+p_r=\max\limits_{i=l}^rp_i

同样考虑分治。设当前分治区间为 [L,R]，中点 mid=\left\lfloor\dfrac{L+R}{2}\right\rfloor。考虑计算跨过中点的区间个数。

对于右半区间，记录 pre_x=\max\limits_{u=mid+1}^x p_x。用同样的套路，从右往左扫描左端点 i，记录 maxn = \max\limits_{u=i}^{mid} p_u。维护一个单调不降的指针 k 使得当右端点 j\in(mid,k) 时，\max\limits_{u=i}^j = maxn；当 j\in[k,R] 时，\max\limits_{u=i}^j = pre_j。

注意到 maxn-p_i,pre_j-p_j\ge 0，因此直接开数组维护桶就行了。k 右移时（下面的 k 是右移前的 k），将 mp1_{p_k}\leftarrow mp1_{p_k}+1，mp2_{pre_k-p_k}\leftarrow mp2_{pre_k-p_k}-1。原因和前几题也是类似的，你就考虑 k 这个位置被放到哪个区间了。

边界：当 L=R 时，返回 0。

时间复杂度为 \mathcal{O}(n\log n)，空间复杂度为 \mathcal{O}(n)。

提交记录（含代码）

Ⅴ - P4755 Beautiful Pair

  • 给定长度为 n 的序列 a_1\sim a_n，求有多少个区间 [l,r] 满足 a_l\cdot a_r\le \max\limits_{i=l}^r a_i 。

考虑分治，设当前分治区间为 [L,R]，中点 mid=\left\lfloor\dfrac{L+R}{2}\right\rfloor。考虑如何统计跨过中点的贡献。

考虑 mid\rightarrow L 扫描左端点 i，统计怎样的右端点 j\,(j\in(mid,R]) 合法。

预处理数组 pre_x=\max\limits_{u=mid+1}^x ，在扫描的过程中同时记录 mx=\max\limits_{u=i}^{mid}a_u。

维护一个单调的指针 k 使得当 j\in(mid,k) 是区间最大值为 mx，j\in[k,R] 时区间最大值为 pre_j。

当 j\in (mid,k) 时，条件可以改写成 a_j\le \left\lfloor\dfrac{mx}{a_i}\right\rfloor；当 j\in[k,R] 时，条件可以改写成 \left\lfloor\dfrac{pre_j}{a_j}\right\rfloor\ge a_i。

那么就用两棵动态开点线段树维护 (mid,k) 中 a_j 每种权值的个数以及 [k,R] 中 \left\lfloor\dfrac{pre_j}{a_j}\right\rfloor 每种权值的个数。k 移动时处理这个位置的变化量。

边界 L=R 时，答案为 1。

注意清空。可以把所有用到的节点放到一个容器里面再单独拿出来清空。

设值域为 V，时间复杂度为 \mathcal{O}(n\log n\cdot \log |V|)，空间复杂度为 \mathcal{O}(n\log |V|)。

提交记录 代码

Ⅵ - ABC248Ex Beautiful Subsequences

  • 给定长度为 n 的排列 a_1\sim a_n 以及整数 k，求有多少个区间 [l,r] 满足 ：
\max\limits_{i=l}^r a_i-\min\limits_{i=l}^r a_i \le r-l+k

考虑分治，设当前分治区间为 [L,R]，中点 mid=\left\lfloor\dfrac{L+R}{2}\right\rfloor。考虑如何统计跨过中点的贡献。怎么全都是这句。

考虑 mid\rightarrow L 扫描左端点 i，统计怎样的右端点 j\,(j\in(mid,R]) 合法。

预处理数组 pmx_x=\max\limits_{u=mid+1}^x a_u,pmn=\min\limits_{u=mid+1}^x a_u。在扫描的过程中同时记录 mx=\max\limits_{u=i}^{mid}a_u,mn=\min\limits_{u=i}^{mid}a_u。

维护两个指针 jmx,jmn，使得：

不难发现当 \boldsymbol i 单调递减时，\boldsymbol{jmx,jmn} 单调不降。

分两大种、六小种情况讨论（加粗的是结论）：

我们发现六种情况本质上是四类统计，每一类统计都是二维数点。

具体地，建立四棵主席树 t1,t2,t3,t4，分别对于每个前缀 (mid,p]\,(p\in(mid,R]) 版本，在节点 [l,r] 内维护这个前缀中有多少个 j,j+pmn_j,j-pmx_j,j-pmx_j+pmn_j 的值在 [l,r] 这个范围内。

统计的时候，先看是哪一大类，再对于三种小类，运用结论得到要统计的权值区间，并将 j 所在的范围拆成两个前缀版本相减的形式去做区间求和即可。

边界：当 L=R 时，返回 1。

时间复杂度为 \mathcal{O}(n\log^2 n)，空间复杂度为 \mathcal{O}(n\log n)。据说二维数点的时候有更高明的桶做法，但是我太弱了不会。

提交记录（含代码）