四重存在线段树

禁忌「フォー・オブ・ア・セグメント」！

P3352 [ZJOI2016]线段树

题意

一个长度为 $n$ 的序列 $a$，$q$ 次操作，每次随机选一个 $[1,n]$ 的子区间 $[l,r]$，将 $[l,r]$ 覆盖为其区间 $\max$，问最后序列中每个数的期望。对 $10^9+7$ 取模，$n,q \leq 400$。

题解

比较套路，但着实巧妙。

首先 $E(x) = \int P(E(x) \ge t)dt$，问题转化对于每个 $t$，求每个数 $\ge t$ 的概率，容易发现 $t$ 只用在 $a_i$ 中枚举。

那我就只用关心 $a_i$ 与 $t$ 的大小关系，相当于变成 $01$ 序列了，每次操作是随机选区间，有 $1$ 则盖掉 $1$。不难发现，我只考虑一段极长 $0$ 连续段 $[l,r]$ 的话，它最后一定会被盖成其子区间（前后缀被盖掉一堆 $1$）。

那不妨设一个 $dp_{t,i,l,r}$ 表示，在考虑 $t$ 的大小关系时，这个极长 $0$ 连续段在 $i$ 次操作后被盖成了 $[l,r]$ 的概率。转移非常的暴力，枚举 $l$ 由 $L$ 被盖到，或者 $r$ 由 $R$ 被盖到，或者不动。令 $tot=\dfrac{n(n-1)}{2}$ 表示总区间个数，则第一种的概率是 $p_1(L) = \dfrac{L-1}{tot}$，第二种的概率是 $p_2(R) = \dfrac{n-R}{tot}$，第三种的概率是 $p_3 = \dfrac{l(l-1) + (n-r)(n-r+1) + (r-l+2)(r-l+1)}{2tot}$。不难得出这样的转移：

$dp_{t,i,l,r} = p_3 \cdot dp_{t,i-1,l,r} + \sum_{L <l} p_1(L)dp_{t,i-1,L,r} + \sum_{R >r} p_2(R)dp_{t,i-1,l,R}$

可以前缀和转移，不多说，时间复杂度 $O(n^3q)$，炸裂开。有个突破口就是这个 $t$ 是我在外面枚举的，但不同的 $t$ 内部 $dp$ 的转移方式完全一样，换言之如果把 $t$ 放在最后一维并且省略它，DP 中的元素及其运算就可以看做一个向量（加法对位加，乘法是数乘）。这启示我们把向量的这一维合成一个数，一并转移。

考虑统计答案的方法，假设 $a$ 中第 $k$ 大的值是 $b_k$（特别地 $b_0 = 0$），则 $E(a_i) = \sum\limits_{k=1}^n (b_k - b_{k-1}) (1-\sum\limits_{l,r}^{i \in [l,r]} dp_{b_k,q,l,r})$，把 $t$ 放最后一维并改写得更直观一些：$E(a_i) = b_n - \sum\limits_{k=1}^n \sum\limits_{l,r}^{i \in [l,r]} (b_k - b_{k-1})dp_{q,l,r}[b_k]$。

如果还不够直观，令 $\bf v$ 是向量，定义 $f(\mathbf{v}) = \sum_k (b_k - b_{k-1})\mathbf{v}_{b_k}$，则 $E(a_i) = b_n - \sum\limits_{l,r}^{i \in [l,r]} f(dp_{q,l,r})$。那么我只需要维护向量的 $f$ 值就行，不难发现转移时，有 $f(\mathbf u + \mathbf v) = f(\mathbf u) + f(\mathbf v)$ 和 $f(a\cdot \mathbf u) = a \cdot f(\mathbf u)$，故可以直接套原来的转移。时间复杂度优化至 $O(n^2 q)$。

P6630 [ZJOI2020] 传统艺能

题意

给出一棵 $[1,n]$ 的广义线段树（每个节点的 $mid$ 不一定是中点），$k$ 次操作，每次随机选一个 $[1,n]$ 的子区间进行懒标记操作，即在递归的叶子节点打上标记并清空所有祖先标记，求最后树上期望标记数量，对 $998244353$ 取模，$n \leq 2\times 10^5$, $k \leq 10^9$。

题解

根据期望线性性，枚举每个节点算期望。此时我只关心这该节点上有没有标记，那什么东西会影响该节点的标记？只有它的祖先，并且我只关心是否存在一个祖先拥有标记。所以该节点的状态我可以一个 $0/1$ 变量组 $(a,b)$ 表示，$a$ 是该节点有没有标记，$b$ 表示该节点是否存在祖先有标记。

有个朴素 DP，就是 $f_{i,a,b}$ 表示第 $i$ 次操作时该节点的状态为 $(a,b)$ 的概率，由 $f_{i-1}$ 转移过来。这个可以矩阵乘法优化，时间复杂度 $O(n \log k)$，剩下的就是大分类讨论了（悲）。

P5280 [ZJOI2019]线段树

题意

初始有一棵 $[1,n]$ 的线段树，节点全部没有标记。打标记操作的定义同上题，$m$ 次操作：

1. 把当前所有线段树复制一遍（编号为 $i$ 的复制为 $2i$ 和 $2i+1$），并对编号为奇数的线段树的 $[l,r]$ 打标记；
2. 查询当前所有线段树上的标记数量总和。

对 $998244353$ 取模，$n,m \leq 10^5$。

题解

和上题的思想基本一致的，就是用数据结构维护上题的大分讨。

具体而言，节点上维护一个 $f_{a,b}$ 表示该节点的状态为 $(a,b)$ 的线段树数目，同时维护 $g_{a,b}$ 表示区间和，然后直接在线段树上复现这个修改：

1. 遍历到的 $O(\log n)$ 个节点直接暴力修改了；

2. 无法遍历的节点有两种，在 $[l,r]$ 里/外的，分情况讨论：

   1. 在 $[l,r]$ 里面，有一半线段树会强制把祖先打上标记；

   2. 在 $[l,r]$ 外面，无事发生。

开一棵线段树模拟操作，2-1 这种情况直接在线段树上打标记就好，复杂度 $O(m \log n)$。

P5210 [ZJOI2017]线段树

题意