析合树学习笔记
5k_sync_closer
·
·
个人记录
析合树是一种连续段数据结构。
引入：
给定排列 \{P_n\}，求值域连续的段的个数。
概念
排列 是排列。
连续段 是值域连续的段，满足集合运算。
值域区间 是连续段值域的区间。
本原段 是不与其他连续段部分相交的连续段。
连续段集 I_p，本原段集 M_p。
形式化地，
定义序列 P 是 n 阶排列 \Leftrightarrow|P|=n 且 \forall i\in[1,n],i\in P。
定义 (P,[l,r]) 是连续段 \Leftrightarrow\nexists x,z\in[l,r],y\notin[l,r],P_x<P_y<P_z。
连续段 (P,[l,r]) 满足 [l,r] 上的集合运算。
定义 (P,[l,r]) 的值域区间为 [\min\limits_{i=l}^rP_i,\max\limits_{i=l}^rP_i]。
定义连续段集 I_p=\{A|A\ \text{是连续段}\}。
定义连续段 X 是本原段 \Leftrightarrow\forall A\in I_p,X\cap A=(P,\varnothing) 或 X\subseteq A 或 A\subseteq X。
定义本原段集 M_p=\{A|A\ \text{是本原段}\}。
析点与合点
析合树的点集是 M_p。
概念
节点 u 的 值域区间 为 [u_l,u_r]。
节点 u 的 子节点序列 S_u 是 u 的极长真子本原段序列。
节点 u 的 子节点排列 P_u 是 S_u 按值域区间左端点离散化的结果。
节点 u 是 合点 当且仅当 P_u 有序。
节点 u 是 析点 当且仅当 u 不是合点。
形式化地，
定义节点 u 的值域区间为 [u_l,u_r]。
定义节点 u 的子节点序列 S_u=\{v|v\subsetneqq u,\nexists
w\subsetneqq u,v\subsetneqq w\}，且按 v 的左端点排序。
注意，v 的左端点不是 v 的值域区间左端点。
定义节点 u 的子节点排列 P_{u,i}=|\{v_l\le{S_{u,i}}_l|v\in S_u\}|。
定义节点 u 是合点 \Leftrightarrow\forall i\in[1,|S_u|],P_{u,i}=i 或 \forall i\in[1,|S_u|],P_{u,i}=|S_u|-i+1。
定义节点 u 是析点 \Leftrightarrow u 不是合点。
性质
$u$ 是合点当且仅当 $S_u$ 的子段构成连续段。显然。
$u$ 是析点当且仅当 $S_u$ 的多元素**真**子段不构成连续段。
证明：若命题不成立，则 $S_u$ 构成连续段的极长**真**子段构成本原段，而此本原段未在析合树中出现。
形式化地，
$\bigcup\limits_{v\in S_u}v=u$。
$u$ 是合点 $\Leftrightarrow\forall [l,r]\subseteq[1,|S_u|],\bigcup\limits_{i=l}^rS_{u,i}\in I_p$。
$u$ 是析点 $\Leftrightarrow\forall [l,r]\subseteq[1,|S_u|],l<r,\bigcup\limits_{i=l}^rS_{u,i}\notin I_p$。
# 建树
可以用 **增量法** $O(n\log n)$ 建析合树。
将 $P_i$ 依次加入析合树，用一个栈维护 $P_j|j\in[1,i]$ 形成的析合森林。
### 策略
维护当前 $i$ 所在子树的根 $u$（初值为 $(P,[i,i])$），考虑 $u$ 与栈内节点的合并情况。
1. $u$ 能成为栈顶节点的子节点 $\Leftrightarrow$ 栈顶节点是合点且 $u$ 与栈顶节点的**最右**子节点能合并成连续段，令 $u$ 成为栈顶节点的子节点，然后令 $u\gets$ 栈顶节点。
2. $u$ 不能成为栈顶节点的子节点，令 $u$ 与栈顶若干节点合并成连续段 $v$ 且 $|S_v|$ 最小。考虑 $v$ 的类型，容易发现此时 $v$ 是合点 $\Leftrightarrow |S_v|=2$。令 $u\gets v$。
3. 重复上述方案直到不能进行（即找不到 2. 中合法的 $v$），将 $u$ 入栈。
（来自 CF，对 $\{9,1,10,3,2,5,7,6,8,4\}$ 建析合树）
根据上述策略，我们需要快速判断 $u$ 与一些点能否合并成连续段，即判断任意后缀 $[j,i]|j\in[1,i]$ 是否连续段。
### 子问题
考虑如何快速判断 $[j,i]|j\in[1,i]$ 是否连续段。
$P$ 是排列，所以 $[j,i]$ 是连续段当且仅当 $\max\limits_{j\le k\le i}P_k-\min\limits_{j\le k\le i}P_k=i-j$。
维护 $Q_j=\max\limits_{j\le k\le i}P_k-\min\limits_{j\le k\le i}P_k-i+j|j\in[1,i]$，则 $[j,i]$ 是连续段当且仅当 $Q_j=0$。
考虑更新 $i$ 时如何快速更新 $Q$。
在 $\max\limits_{j\le k\le i}P_k-\min\limits_{j\le k\le i}P_k-i+j$ 中，$j$ 是不变的，每次更新 $i$ 对 $Q_j$ 的贡献减一，最值的贡献不好维护。
设 $P_i$ 更新了 $B_i$ 个后缀最值的**位置**，注意到 $\sum\limits_{i=1}^nB_i=O(n)$（单调栈结论）。
用单调栈维护后缀最值的位置，以后缀最小值为例。
维护单调递增的栈 $x$。不难发现 $P_{x_i}$ 是后缀 $[j,i]|j\in(x_{i-1},x_i]$ 的最小值。
$x_i$ 出栈时失去对 $Q_j|j\in(x_{i-1},x_i]$ 的贡献，所以 $Q_j|j\in(x_{i-1},x_i]\gets Q_j+P_{x_i}$。
$i$ 入栈时获得对 $Q_j|j\in(x_{top},i]$ 的贡献，所以 $Q_j|j\in(x_{top},i]\gets Q_j-P_i$。
后缀最大值同理。
转化为区间加，单点查询，找最左 $0$，线段树维护。
# 例题
>[P8600 [蓝桥杯 2013 省 B] 连号区间数](https://www.luogu.com.cn/problem/P8600) / [CF526F Pudding Monsters](https://www.luogu.com.cn/problem/CF526F)
>
>给定**排列** $\{P_n\}$，求值域连续的段的个数。
考虑析合树内每个点的贡献。
由合点的性质，若 $u$ 是合点，则 $S_u$ 的任意子段构成连续段，即 $u$ 的贡献为 $|S_u|\choose2$。
由析点的性质，若 $u$ 是析点，则 $S_u$ 的任意多元素子段不构成连续段，即 $u$ 的贡献为 $1$。
注意到 $|M_p|=O(n)$，所以时间复杂度 $O(n\log n)$。
代码：[指针 1.98KB 199ms 8.48MB](https://www.luogu.com.cn/paste/nuq7suag)，[非指针 2.02KB 207ms 9.66MB](https://www.luogu.com.cn/paste/wgexsenq)
------------
一些序列上连续段问题可以转化为析合树上问题。
>[P4747 [CERC2017]Intrinsic Interval](https://www.luogu.com.cn/problem/P4747)
>
>给定**排列** $\{P_n\}$，$m$ 次询问包含某区间的最短连续段。
只讨论**在线**做法。
考虑对询问区间 $[l,r]$，求出 $(P,[l,l]),(P,[r,r])$ 在析合树上的 LCA 为 $u$ 点。
由合点的性质，若 $u$ 是合点，则 $S_u$ 的任意子段构成连续段，$S_u$ 上二分包含 $[l,r]$ 的最短子段即可。
由析点的性质，若 $u$ 是析点，则 $S_u$ 的任意多元素子段不构成连续段，即答案为 $u$。
代码：[非指针 2.79KB 2.65s 33.56MB](https://www.luogu.com.cn/paste/atd7knxb)
------------
>~~没了的 JDOI G~~ ~~LAOI R1 没了的 T4~~ ~~LAOI 没了的入团赛 T4~~ 无中生题
>
>给定**排列** $\{P_n\}$，$m$ 次询问包含某区间的连续段数量。
这题比较饱经风霜，所以题解比较详细（
考虑对询问区间 $[x,y]$，求出 $(P,[x,x]),(P,[y,y])$ 在析合树上的 LCA 为 $u$ 点。
容易发现只有 $S_u$ 和 $\text{root}\to u$ 路径上的点产生贡献。
考虑 $S_u$ 的贡献，即计算有多少 $S_u$ 的**真**子段包含 $[x,y]$。（$u$ 的贡献算到 $\text{root}\to u$ 路径上）。
若 $u$ 是合点则 $S_u$ 上二分，若 $u$ 是析点则贡献为 $0$。
（$u$ 是合点的情况）
维护树上前缀和数组 $v_u$ 表示 $\text{root}\to u$ 路径的贡献。
令 $c=S_{u,i}$，考虑 $c$ 这一层对 $v_c$ 的贡献。
若 $u$ 是合点即统计有多少 $S_u$ 的**真**子段包含 $c$，跟上面完全一致，就不画图了。
若 $u$ 是析点则贡献为 $1$，即 $c$ 本身。
不难得到递推式：
$$
v_c=
\begin{cases}
v_u+i(|S_u|-i+1)-1&u\ \text{是合点（考虑包含 c 的真子段数量）}\\
v_u+1&u\ \text{是析点（析点的性质）}
\end{cases}
$$
两部分贡献加起来即可。
代码：[非指针 2.94KB 2.30s 140.51MB](https://www.luogu.com.cn/paste/zp8ry52y)
众所周知析合树的题都可以不用析合树做，所以如果有人会不用析合树做这个可以私我（
------------
>[CF997E Good Subsegments](https://www.luogu.com.cn/problem/CF997E)
>
>给定**排列** $\{P_n\}$，$m$ 次询问某区间包含的连续段数量。
只讨论**在线**做法。
相当于区间 CF526F，所以考虑类似想法。
定义析合树内每个点的贡献：
>由合点的性质，若 $u$ 是合点，则 $S_u$ 的任意子段构成连续段，即 $u$ 的贡献为 $|S_u|\choose2$。
>
>由析点的性质，若 $u$ 是析点，则 $S_u$ 的任意多元素子段不构成连续段，即 $u$ 的贡献为 $1$。
定义 $S_u$ 上区间 $[l,r]$ 的价值为其中每个点的子树贡献和之和，若 $u$ 是合点，还要加上 ${r-l+1\choose 2}$。
考虑询问 $[x,y]$ 时，统计 $[x,y]$ 包含的极大 $S_u$ 上区间价值和。
设 $(P,[x-1,x-1])$ 为 $u$ 点，$(P,[y+1,y+1])$ 为 $v$ 点，$l=\operatorname{lca}(u,v)$，
$U$ 为 $u$ 的 $dep_u-dep_l-1$ 级祖先，$V$ 为 $v$ 的 $dep_v-dep_l-1$ 级祖先。
（黑色线段表示一个节点，红色，绿色线段表示需要统计的区间）
**对于红色线段：**
对于所有 $u$ 到 $U$（不含 $U$）的路径上的点 $o$，设 $o$ 在 $S_{fa_o}$ 的第 $i$ 位，则 $S_{fa_o}$ 上区间 $(i,|S_{fa_o}|]$ 被 $[x,y]$ 包含，需要统计其价值。
同理，对于所有 $v$ 到 $V$（不含 $V$）的路径上的点 $o$，设 $o$ 在 $S_{fa_o}$ 的第 $i$ 位，则 $S_{fa_o}$ 上区间 $[1,i)$ 被 $[x,y]$ 包含，需要统计其价值。
定义 $u$ 的点权为 $u$ 在 $S_{fa_u}$ 上的前 / 后缀（不含 $u$）价值，则转化为求静态树链点权和，树上前缀和维护之。
**对于绿色线段：**
设 $U$ 在 $S_l$ 的第 $L$ 位，$V$ 在 $S_l$ 的第 $R$ 位，则 $S_l$ 上区间 $[L+1,R-1]$ 被 $[x,y]$ 包含，需要统计其价值。
则转化为求 $S_l$ 区间价值，维护每个 $S_u$ 的前缀子树贡献和之和、每个点 $u$ 在 $S_{fa_u}$ 上的排名即可。
代码：[非指针 3.33KB 685ms 51.67MB](https://www.luogu.com.cn/paste/2whs9r0b)
比较不理解为什么 7s，放根号过去？
~~CF526F \*3000，这个也 \*3000？加个强制在线绝对不止~~
区间最长连续段维护方法相同，这里不再赘述。
# 闲话
析合树是可以 $O(n)$ 建树的……但是我不会
所以 CF526F 和 CF997E（Tarjan 求 LCA）都是可以 $O(n)$ 做的，比很多非析合树做法好（
但是看起来代码复杂度会巨大，先咕着。