谢罪环节：

这次题目疑似组难了，码量也不太平衡。总之祝大家省选顺利（

最小表示法

来源：

• https://qoj.ac/problem/1855

拆成若干次计算 $[f(a_i) = f(a_{i+1})]$。

对于长度为 $n$ 的串，若循环节为 $d$，则 $f(s) = 1\sim d$ 的概率都为 $\frac{1}{d}$。

设 $g(n)$ 为循环节为 $n$、长度为 $n$ 的串个数，可以容斥得到 $g(n) = \sum_{d|n}26^{d}\mu(\frac{n}{d})$。

$P(f(n)=k)$ 可以分为 $d_0(n)$ 个值相等的连续段，对每个连续段算概率即可。

时间复杂度 $O(n d_0(V))$。

注意特判 $n=1$。

二叉搜索树

来源：

• https://qoj.ac/problem/971 加强版

首先把询问离线。考虑在链上怎么做：

考虑差分，维护两棵相邻 BST 之间的变化。扫描线，在 $[l,r]$ 加入插入操作，相当于 $l$ 时加入了一个插入操作，$r+1$ 时删除了一个插入操作。

考虑对于一个 $x$，哪些点是 $x$ 的祖先？

对于所有比 $x$ 大的数 $y$，把 $y$ 按照值从小到大排序，一个一个扫，设 $now=t_x$，如果 $t_y < now$ 则 $y$ 记入 $x$ 的祖先，并且 $now \to \min(now,t_y)$。也就是所有使 $now$ 变小的点的权值。

以权值为下标、时间为值建线段树，那上面要求的信息就是套用楼房重建，前缀最大值线段树的做法。

对于比 $x$ 小的 $y$，就是 $y$ 按照值从大到小排序，一个一个扫。于是维护两棵前缀最大值线段树即可。

在树上的做法：

直接树链剖分，对每条链套用链的做法，时间复杂度 $O(q\log^3 n)$，期望得分 72 或 100，被 hos_lyric 卡过去了。

既然在链上的做法是差分，那也可以套用到树上做树上差分。发现维护的信息就是在线段树上做，可以做树上差分+线段树合并。时间复杂度 $O(q\log^2 n)$，期望得分 100。

算法 2 by gqh

先发现答案的形式比较简单，只和x<=query的tim后缀最小值有关，x>query同理。

然后离线下来对x排序用吉司机线段树对time去checkmin即可。

虽然是 $q\log n$ 次区间checkmin，但是复杂度仍然是 $O((n+q)\log^2 n)$。

黑白球染色

来源：

• https://qoj.ac/problem/9438

相当于有一个直方图，图内的格子必须是 $0$，外面的格子可以是 $0/1$。（这里把 $a_i$ 翻转了，变成 $\le a_i$ 的必须是 $0$）

每个 $0\to 0$ 之间必须 xor 偶数次，$0$ 到末尾 xor 偶数或奇数次都行。

假设对于这每个绿色的区间都求出一个多项式 $f(x)$，$f(x)[x^i]$ 表示在区间内操作了 $i$ 次的方案数。

从下到上做，每个区间就是下面一层子区间一堆多项式乘起来，然后再乘一个变换。

这个变换在多项式上是 $F(x) \to \frac{(F(x+1)+F(x-1))}{2}$。

由于最终答案是最上面那个多项式的 $F(0)$，所以最下面多项式维护点值 $F(-m...m)$，往上一层能求出 $F(-(m-1)..(m-1))$，直到最上面一层能求出 $F(0)$，就行了。

开 $m$ 棵线段树，维护每一层的每个区间的 $F$ 值，以及 $F$ 值的区间乘积。修改一个 $a_i$ 时，只会有 $O(m)$ 个区间的 $F$ 值要重新计算。

时间复杂度 $O(qm^2\log n)$。

另一个做法：https://www.cnblogs.com/275307894a/p/18450179