省选准备?

P3726 [AH2017/HNOI2017] 抛硬币

要求

$$
\sum_i \sum_j [j<i] \binom{a}{i}\binom{b}{j}
$$

这就不会了, 然而这是双射题, 考虑 $a=b$ 的时候赢的翻转能映输的, 就只需要求平局的 $\sum_i \binom{a}{i}^2$ 是经典问题.

现在 $a>b$, 设实际各证明 $x, y$ 次, 则 $a$ 输/平的翻转都会变成赢($x\le y, a-x>b-y$), 而问题就是A赢的可能仍然是赢, 这种情况要求 $a-x>b-y, x>y$, 于是 $x-y\in [0, a-b]$, 而 $a-b$ 很小, 枚举个差, 就是 $\sum_d \sum_i \binom{a}{i+d}\binom{b}{i}=\sum_d \sum_i \binom{a}{i+d}\binom{b}{b-i}=\sum_d \binom{a+b}{b+d}$ 暴力算就行了.

最后你需要用exlucas算组合数

P5279 [ZJOI2019] 麻将

dpofdp, 先考虑如何判定是否胡牌, 那么顺子这种性质肯定是扫值域, 从小到大, 设 $f_{i, j, 0/1}$ 表示前 $i$ 种牌, 形成 $j$ 个 $i, i-1$ 的对, 是否已经出现刻字, 转移显然, 可以对着转移建自动机.

发现节点并不对, $S\approx 2000$ 个

然后求期望可以累加前缀 $1\ldots i$ 加入之后还没胡的概率, 于是 $f_{i, j, k}$ 表示前 $i$ 种牌, 一共加入了 $j$ 张牌, 走到自动机的节点 $k$ 的期望步数.

转移是枚举当前种牌加了多少张, 复杂度是 $n^2S$ 的.

P3307 [SDOI2013] 项链

先数珠子有几种, 正三棱柱的置换包括3种, 横着转一/二下和左右翻转, 只要数互质数对个数, 莫反板子.

然后数项链是模板ploya吧?

P4916 [MtOI2018] 魔力环

先上一套burnside, 现在变成要求对每个 $d$, 设 $l=gcd(d, n)$, 求 $f_l$ 表示长 $l$ 的环(不可旋转), 有 $\dfrac{mn}{l}$ 个黑色珠子, 不能连续出 $k$ 个黑色的方案数.

先把白色放好开始插入黑色, 枚举插入的空隙数, 设黑色个数为 $b$, 得到

$$
\sum_i \binom{l-b}{i}g(b, i)
$$
于是求 $g(n, c)$ 表示把 $n$ 个不区分的球分成 $c$ 个区分的盒子每份大小不超过 $k$ 的方案数, 于是

$$
g(n, c)=x^n^c=(1-x^{k+1})^c(1-x)^{-c}=(\sum_i \binom{c}{i}x^{ik+i})(\sum_i \binom{c+i-1}{i}x^i)
$$

于是可以 $\dfrac{n}{k}$ 算一项, 而枚举插入的空隙数是 $O(k)$ 的, 所以算一次是 $O(m)$, 于是算所有 $f$ 的复杂度是关于 $n$ 约数和线性, 而约数和最大是 $n\log n$ 的(根号为界分开分析), 于是总复杂度是单log的.

[ARC120F] Wine Thief

考虑对每个元素计算贡献, 要算挖去一个区间后两边选 $k-1$ 个元素的方案数. 是两边的方案卷起来, 不可做.

考虑设从 $n$ 个中选 $i$ 个且满足限制的方案数为 $f_{n, i}$, 从 $n$ 个中选 $i$ 个且第 $j$ 个强制选的方案数为 $g_{n, i, j}$, 则对于 $i\in [D, n-D+1]$, $g_{n, i, j}$ 就是先选一个 $j$, 然后要求 $[j-D+1, j+D-1]$ 这块不能选, 相当于挖掉这块添加一个长 $d$ 的空段(使得两边互不影响), 那么你不能选到空段上, 于是 $g_{n, i, j}=f_{n-D, i-1}-\sum_{k\in [i, i+D-1]} g_{n-D, i-1, k}$.

这可以看成卷积: $G_{n, i}(x)=\sum_j x^j g_{n, i, j}$, 则 $G_{n, i}=\dfrac{1}{1-x}f_{n-D, i-1}-G_{n-D, i-1}*(\sum_{j=0}^d -x^{-j})$

而初始状态应该是 $G_{n-kD, 0}=0$, 每次区间加并卷上一个平移的多项式, 对于变换 $m$ 次的多项式, 发现满足性质前 $mD$ 项和后 $mD$ 项对称相等而中间全部相等, 于是直接卷起来复杂度就从 $n^2\log n\log k$ 变为 $n\log n\log k$

P4500 [ZJOI2018] 树

考虑要求 $\sum_{a\in A} s^k(a)$, 其中 $s(a)$ 为 $a$ 这一无根树对应有标号树个数, 则要设出乘法/加法复合意义的GF, 设 $a$ 的GF为 $F_k(a)=\dfrac{s(a)^k x^{\vert a\vert}}{(\vert a\vert! )^k}$, 容易发现满足条件, 而一个组合类的GF自然是 $F_k(A)=\sum F_k(a)=\sum_i \dfrac{f_ix^i}{(i! )^k}$.

则现在建立树形方程, 有 $\mathrm{xD}F=\mathrm{MSET} F$, 其中 $\mathrm{xD}, \mathrm{MSET}$ 分别是使组合类大小减少 $1$ 和多重集构造.

考虑推出这个特殊GF的 $\mathrm{MSET}$, 则显然是

$$
\begin{gathered}
\mathrm{MSET}(A)
=\prod_{a\in A} \sum_{i=0} \dfrac{s(a)^{ki}x^{\vert a\vert i}}{(i! )^k(\vert a\vert! )^i}
=\exp \sum_{a\in A} \ln \sum_{i=0} \dfrac{s(a)^{ki}x^{\vert a\vert i}}{(i! )^k(\vert a\vert! )^i}\
let\ G(x)
=\ln \sum_{i=1} \dfrac{x^i}{(i! )^k}
\
\mathrm{MSET}(A)
=\exp \sum_a G(\dfrac{s(a)^{k}x^{\vert a\vert}}{(\vert a\vert! )})\
=\exp \sum_a \sum_{i=1} g_i \dfrac{s(a)^{ki}x^{\vert a\vert i}}{(\vert a\vert! )^i}\
=\exp \sum_{i=1} g_i \sum_a \dfrac{s(a)^{ki}x^{\vert a\vert i}}{(\vert a\vert! )^i}\
=\exp \sum_{i=1} g_i F_{ki}(x^i)
\end{gathered}
$$

于是有

$$
\mathrm{xD} F=\exp \sum_{i=1} g_{i} F(x^i)\
\ln (\mathrm{xD} F)-g_1F(x)=\exp \sum_{i=2} g_{i} F_{ki}(x^i)
$$

于是可以提取系数递推了, $F_i$ 从大到小推, 则推 $F_{i}$ 时, $F$ 只用推到第 $\dfrac ni$ 项, 于是等号左边推 $\exp$ 和右边算 $\ln$ 得到 $g$ 的复杂度是 $\sum_i \dfrac{n^2}{i^2}=O(n^2)$, 而右边的求和只求 $\sum_i \dfrac{n}{i}\ln \dfrac{n}{i}=n\ln^2 n$ 项即可.

总复杂度 $n^2$

重点应该是构造满足乘法性质的特殊GF并整出对应运算.

[ARC154F] Dice Game

应该想到叶开WC的论文选讲!

列GF, 设 $F(x)$ 为 $PGF$, 所求即 $F(e^x)$, $F(x)$ 应该枚举最后一次是几得到, 除了最后这次其他的元素用EGF分配时间轴上标号, $L$ 为拉普拉斯变换:

$$
\begin{gathered}
F(x)=L(x(e^{\frac{x}{n}}-1)^{n-1})\
=L\left(
\sum_{i=0} \binom{n-1}{i}(-1)^ix\exp(\frac{ix}{n})
\right)\
\because L(x\exp(\frac{ix}{n}))=L\left(\sum_{j=0} (\dfrac{i}{n})^j\dfrac{x^{j+1}}{j! }\right)\
=\sum_{j=0} (\dfrac{i}{n})^j(j+1)x^{j+1}\
=\dfrac{n}{i}\sum_{j=1}j(\dfrac{ix}{n})^j\
=\dfrac{nx}{i(1-\dfrac{ix}{n})^2}\
\therefore
F(x)=\sum_{i=0} \binom{n-1}{i}(-1)^i\dfrac{nx}{i(1-\dfrac{ix}{n})^2}
\end{gathered}
$$

我们要求 $F(e^x)$, 这里不能先求 $F$ 再复合 $e^x$ 因为 $F$ 其实是无限项 $H/G$ 的形式, $e^x$ 有常数项 $1$ 使得后面的项有贡献, 应该先求 $H$ 和 $G$, 分别复合之后再求逆.

先求 $F$ 的话, 可以考虑求 $F(x+1)$ 的系数, 复合 $e^x-1$, 就没有刚才的问题了.

复合 $e^x$ 怎么做?

$$
F(e^x)=\sum_{i=0} f_ie^{ix}=\sum_i f_i\sum_{j=0} \dfrac{(ix)^j}{j! }
$$

$j!$ 可以最后除, 去掉之后就简单了:

$$
\sum_i f_i\sum_{j=0}(ix)^j=\sum_i \dfrac{f_i}{1-ix}
$$

分治FFT!

[ARC117E] Zero-Sum Ranges 2

考虑前缀和, 折线模型, 相等元素个数, dp扫序列不行自然扫值域, 则从上往下不断插入数, 插入规则是相等相邻的两个数之间必须插入至少一个, 设当前已经用了 $i$ 个数, 已经有 $j$ 对相等, 当前能插入的位置有 $k$ 个, 转移时这一层插入几个数 $c$, 则 $f_{i, j, k}\to f_{i+c, j+\binom{c}{2}, c-k-2}$($-2$ 是序列两端必须插入一个), 转移系数是 $c$ 个数放到 $k+2$ 个盒子中, 即 $\binom{c-1}{k+1}$.

然后这样求出的是所有值都在某条线上的, 于是按照 $\ge 0, <0$ 部分合并即可: $\sum_{i, j, k} f_{i, j, k}f_{2n-i, K-j, k-1}$

复杂度是 $n^5$

[ARC096E] Everything on It

$\ge 2$ 这个 $2$ 很小, 考虑容斥, 先容斥没有选恰好一次的数的方案数:

$$
f_n=\sum_c \binom{n}{c}(-1)^c \cdot 2^{2^{n-c}}\sum_i {c\brace i} 2^{(n-c)i}
$$

再容斥没有不选的

$$
\begin{gathered}
ans=\sum_k \binom{n}{k}f_k (-1)^{n-k} \
=\sum_{k=0}^n \binom{n}{k} (-1)^{n-k} \sum_{c=0}^k \binom{k}{c}(-1)^c \cdot 2^{2^{k-c}}\sum_{i=0}^c {c\brace i} 2^{(k-c)i}\
a=n-k+c\
ans=\sum_{a=0}^n (-1)^a \sum_{c=0}^a \binom{n}{a}\binom{a}{c}2^{2^{n-a}}\sum_{i=0}^c {c\brace i}2^{(n-a)i}\
=\sum_{a=0}^n(-1)^a2^{2^{n-a}}\binom{n}{a}\sum_{i=0}^n2^{(n-a)i}\sum_{c=i}^n\binom{a}{c}{c\brace i}
\end{gathered}
$$

注意 $\binom{a}{c}{c\brace i}$ 的组合意义, 即选择 $c$ 个元素再划分成 $i$ 组, 那么剩下的元素划分成一组, 再添加一个元素用来标识这个组, 即这个式子等于 ${a+1\brace c+1}$ 于是做完了.

[ARC119F] AtCoder Express 3

走的过程一定最多往回走一格切换颜色方便往后跳. 考虑已知划分的话怎么求最短路, 可以记录前 $i$ 个点中最后一个 $A/B$ 类点(包括自己)到起点距离 $d_0, d_1$, 设当前点为 $A$ 类, 若下个点为 $A$ 类则 $d_0’=d_0+1, d_1’=d_1$, 否则 $d_0’=\min(d_0, d_1+2), d_1’=\min(d_0+1, d_1+1)$. 于是dpofdp思想可以得到一个 $n^3$ 的状态: $f_{i, j, k, c}$ 表示填到第 $i$ 个位置, $d_0, d_1$ 和当前点颜色.

感觉可能这种题都跑dfa最小化能赢. 接下来两种走法, 一种是人脑出等价且更小的自动机, 一种是发现性质, 对于一个 $A$ 类点首先总有 $d_0\ge d_1-1$ 因为当前点是由这个 $B$ 点后一格格走的. 而如果 $d_1<d_0-2$, 那么以后一定直接用这个 $d_1$ 的B类点跳过去更好, 所以这样的都和 $d_=d_0-2$ 的等价, 于是就只有 $n^2$ 状态了.

后面这个分析感觉很像小N的独立集? 但是树上问题显然不能搞dfa.

P5206 [WC2019] 数树

好强的题.

想到容斥, 此时能想到对两棵树的集合容斥, 但系数不好确定, 不如对两棵树的边的交集大小容斥.

然后因为是交集求 $\sum_A\sum_B f(A\cap B)$, 我们希望有一种容斥是 $f(S)=\sum_{T\subseteq S} f(T)c(T)$.

[trick]

$f(S)=\sum_{T\subseteq S}\sum_{P\subseteq T}f(P)(-1)^{\vert T\vert-\vert P\vert}$.

证明:
$$
\begin{gathered}
=\sum_{P\subseteq S} f(P)\sum_{T\supseteq P}(-1)^{\vert T\vert-\vert P\vert}\
=\sum_{P\subseteq S} f(P)\sum_{i=0}^{\vert S\vert-\vert P\vert} \binom{\vert S\vert-\vert P\vert}{i}(-1)^i\=f(S)
\end{gathered}
$$

有了这个的话会很好, 比如对于subtask3:

$$
\begin{gathered}
ans=\sum_A \sum_B \sum_{S\subseteq A\cap B}\sum_{T\subseteq S} (-1)^{\vert S\vert-\vert T\vert}y^{n-\vert T\vert}\
=\sum_S \sum_{T\subseteq S} y^{n-\vert T\vert}(-1)^{\vert S\vert-\vert T\vert}\sum_{A\supseteq S}\sum_{B\supseteq S}\
=\sum_S F(S)^2 \sum_{T\subseteq S} y^{n-\vert T\vert}(-1)^{\vert S\vert-\vert T\vert}\
=y^{n}\sum_S F(S)^2 y^{-\vert S\vert}\sum_{T\subseteq S} (-y)^{\vert S\vert-\vert T\vert}\
=y^{n}\sum_S F(S)^2 y^{-\vert S\vert}\sum_i \binom{\vert S\vert}{i}(-y)^{\vert S\vert-i}\
=y^{n}\sum_S F(S)^2 (\dfrac{1}{y}-1)^{\vert S\vert}\
let\ K=\dfrac{1}{y}-1\
ans=y^nn^{-4}K^{n}\sum_P K^{-\vert P\vert} n^{2\vert P\vert} \prod_i p_i^2
\end{gathered}
$$

$P$ 是枚举划分, 则大小为 $i$ 的集合贡献 $\dfrac{n^2}{K}i^i$(一个有 $i^{i-2}$ 种方式组成连通块), exp即可.

对Subtask2, 把上面的转化式子抄一份下来:

$$
ans=y^{n}\sum_{S\subseteq A} F(S) K^{\vert S\vert}\
=y^n K^nn^{-2}\sum_{P\subseteq P_A}K^{-\vert P\vert}n^{\vert P\vert}\prod_{p_i}p_i
$$

树上选连通块, 大小为 $i$ 的连通块贡献 $w=K^{-1}ni$. 考虑dpGF, 设考虑点 $u$ 子树, $u$ 所在连通块为 $i$ 的方案数为 $[x^i]H_u$(常数为 $0$)转移是 $H_u: =H_uH_v+KH_v’(1)H_u$(第一个是并入连通块, 第二个是这里断开乘上贡献), 对这个式子求导带入1得到:

$$
H_u’(1)=H_u’(1)H_v(1)+H_v’(1)H_u(1)+KH_v’(1)H_u’(1)
$$

答案只要用到 $H_1(1)$, 于是只要维护 $H’_u(1)$ 和 $H_u(1)$ 即可做到线性. 可以用来维护转移是GF, 最后要点值的dp.

[AGC058D] Yet Another ABC String

GF熟练题, 容斥好题.

首先最好想的做法是, 建出一个简单的DFA去匹配这 $3$ 个串, 每个点设一个 $3$ 元GF $F_i(x, y, z)$, 可以简化到 $3$ 个GF方程, 转移很好写, 就是要解一个很麻烦的GF方程再很麻烦的提取系数.

更简单的做法是直接GF凑容斥系数, 题目相当于可以用若干个长度不超过 $2$ 的连续段拼出这个序列, 设长 $i$ 的段系数为 $a_i$, 我们希望 $\dfrac{1}{1-(\sum_i a_ix^i)}=1+x+x^2$, 设 $a_i$ 的GF为 $A$. 然后是求 $\dfrac{1}{1-B(x, y, z)}$, $[x^iy^jz^k]B=[x^{i+j+k}]a$.

更简单的容斥, 容易想到对极长的段 $l, r$ 容斥, 其中 $[l, r]$ 是 $abc$ 不断循环的区间, 但只对这样的段的个数容斥的话, 其实方案数很好求, 因为只要确保段长大于等于 $3$, 可以直接组合数.

[ARC100F] Colorful Sequences

拆贡献! 考虑 $[p, p+M]$ 恰为 $A$ 的满足第一个限制的序列数量. 那么分类:

$A$ 包含长 $k$ 两两不同的子区间: 显然.
$A$ 中有相同元素, 设极长无相同元素的前缀, 后缀为 $a, b$, 容斥求不合法的, 设 $f_{i, j, 0/1}$ 表示从 $p+M+1$ 或 $p-1$ 开始, 长 $j$ 的区间包含 $j$ 种不同的元素, 且不出现长 $k$ 的互不相同段的方案数, 初始状态 $(0, p)=1, (0, q)=1$, 是否已经存在满足要求的区间, dp完了卷起来即可.
$A$ 中无相同元素但长度不足 $k$, 此时所有长度相同的 $A$ 本质相同, 此时发现不如不钦定位置, 直接算一个序列长度等于 $m$ 的合法区间的个数的期望, 设 $f_{i, j}, g_{i, j}$ 分别表示方案数和期望即可.

CF1086F Forest Fires

应该是典的了, 考虑矩形并可以写成容斥的式子, 而任意个矩形的交也是一个不断扩散变大的矩形, 随时间也是二次函数, 于是某个时刻 $t$ 的格子个数就会了, 而最后答案就是对这个时间区间求和, 也就变成三次函数, 做完了, 拉插即可. 分段函数当且仅当两个矩形出现交的 $n^2$ 个时间点变化.

P7468 [NOI Online 2021 提高组] 愤怒的小 N

感觉这个作差推式子的思路不太熟.

容易想到dp, 设 $A_i(x)$ 表示迭代 $i$ 次后, 设 $a$ 位置集合为 $S$, $\sum_{i\in A}f(i+x)$ 的值, 同理设 $B_i(x)$, 有 $A_{i+1}(x)=A_i(x)+B_i(x+2^i), B_{i+1}(x)=B_i(x)+A_i(x+2^i)$, 但是直接做是 $nk^2$(最多大常数 $nk\log n$)的.

此时, 因为式子形式对称又线性, 考虑作差, $D_{i+1}(x)=A_{i+1}(x)-B_{i+1}(x)=A_i(x)-B_i(x)-A_i(x+2^i)+B_i(x+2^i)=D_i(x)-D_i(x+2^i)$, 而重点是, 这样做一定会消掉最高次项, 于是迭代 $k$ 次后就 $D(x)=0$.

可以 $n^3$ 算出所有 $D$, 而我们要求的是若干段 $A$ 的值, 我们知道 $A_i(x)+B_i(x)=\sum_j^{2^i}f(x+j)$, $A+\dfrac{A+B+D}{2}$, $D$ 已经解决, 只要求 $A+B$, 简答画式子得到就是 $\sum_{i=0}^N f(i)$, 于是拉插做完了.

[trick] 作差是关键一步, 对形式对称的递推式考虑其和, 差式子的递推式.

[ARC142D] Deterministic Placing

容易发现一定是来会跳, 但要想到对于若干条不交的链跳起来互不影响, 于是就算求把树划分成若干条链的带权方案数, 有 $k$ 条链的权值为 $2^k$.

有了这个后下面的是模板树形dp, 有点讨论, 复杂度线性.

[ARC111F] Do you like query problems?

[think] 既想着序列上拆期望贡献, 值域上拆期望也别忘了.

困难是某次求和可能和前面一个遥远的位置有关, 考虑拆贡献, 每个位置单独计算, 且按值域拆成是否大于 $i$, 然后写式子就行了.

[ABC241Ex] Card Deck Score

简单题, 显然多项式是

$$
\prod_i \dfrac{1-(a_ix_i)^{b_i+1}}{1-(a_ix_i)}
$$

于是分子分母乘起来, 分子只有 $2^16$ 项, 每项要想贡献到 $[x^m]$ 对应的分母那项是确定的, 也就是 $2^16$ 个对 $\prod_i \dfrac{1}{1-(a_ix_i)}$ 求远处系数的询问, 显然部分分式做完了.

[ARC135E] Sequence of Multiples

显然 $a_i=\lfloor \dfrac{a_{i-1}}{i}\rfloor i+i$ 考虑 $b_i=\dfrac{a_i}{i}$, 则 $b_i=1+\lfloor \dfrac{b_{i-1}(i-1)}{i}\rfloor=b_{i-1}+1-\lceil \dfrac{b_{i-1}}{i}\rceil$, 于是 $b_{i-1}-b_i=\dfrac{b_{i-1}}{i}-1$, 是不增的(上取整). 分析 $b$ 的上界, $a_i\le x+\sum_{j=2}^i j\le x+i^2$, $b_i\le \dfrac{x}{i}+i$, 于是 $b_i-i$ 是有根号分治的, 但数据范围看起来要整到 $\sqrt[3] n$.

[trick] $\dfrac{x}{i-1}-\dfrac{x}{i}$ 的不同值的个数是 $\sqrt[3] n$ 的, 通分一下和 $\dfrac{x}{i^2}$ 是同级的.

于是就做完了.

见到这种玩意打表找规律就对了/fn另外就是没规律就差分.

[ARC093F] Dark Horse

显然每个位置概率相等, 钦定你在 $1$, $1$ 的祖先上会进行 $N$ 次比赛, 而且这些点之中编号小的胜利, 也就是剩下的点大小为 $1\ldots 2^{n-1}$ 的组, 每组的最小值不为 $A_i$. 考虑容斥, 钦定一个最小值相当于一个值域限制. 从小到大填数, $f_{i, S}$ 表示填前 $i$ 大的数, $S$ 中的组填过数(最小值确定), 问题是不能把剩余大小设进去, 于是想每次填满一整组, 于是从大往小dp, 每次可以选择把当前 $A_i$ 填到一个组中并把剩下元素选了, 或者什么也不做等着被更小的 $A$ 塞到组里.

复杂度 $2^nnm$

[AGC058F] Authentic Tree DP

很神奇的东西啊

给奇怪的式子找一个组合意义, 乘法看成概率, 则它描述了删一条边, 剩余两个连通块分别满足性质的概率, 区别是分母应该是 $n-1$, 若是则答案是 $1$, (把一棵树删空的概率). 两边的问题是独立的,

于是考虑给点/边赋权让系数总和是 $n$ 且仍然有组合意义, 改成删点, 每个点有 $1$ 的权重, 每个边建一个点有 $1$ 的权重, 边点挂一个点有 $-1$ 的权重, 满足了权重和是 $n$. 显然原图上一组删边方案等价于在新图上每次删一个边点的方案, 只要保证边点比相邻的点先删. 所以答案就是这个条件(边点比周围点先删)的概率.

树上双向边拓扑序计数, 容斥典题.

[ABC236Ex] Distinct Multiples

考虑容斥, 钦定若干集合相等, 考虑容斥系数.

一个集合可能被小集合任意组合得到, 而最后只有大小为 $0$ 和 $1$ 的系数是 $1$ 其他的是 $0$, 所以大小为 $i$ 的集合系数是 $[x^i]\ln(1+x)=(-1)^{i-1}(i-1)!$.

则可以算出每个相等集合的方案数, 再集合幂级数exp一下就好了.

P5576 [CmdOI2019] 口头禅

建广义SAM, 则一个点的endpos出现的串形成若干连续段, 一开始连续段数显然 $O(n)$, 用set维护, 启发式合并连续段复杂度是 $n\log n\log v$, 每次合并出新连续段($O(n)$ 次)更新答案(显然只有每个连续段第一次合并出来的时候有贡献因为越浅越短).

另一个做法基于一个结论:

[trick] 广义SAM中设点 $i$ 出现的字符串的集合为 $S_i$, 则 $\sum_i \vert S_i\vert=O(n\sqrt n)$.

于是扫描线, 维护当前 $r$ 的每个向左的连续段, 暴力更新所有含有 $r$ 的端点即可.

P9167 [省选联考 2023] 城市建造

我怎么会没写过这个的题解?

选出点集使得删掉这些点之间的边后每个点恰在一个连通块且限制连通块大小.

考虑性质, 原来的一个连通块只有一个点向外连边, 这个点一定是割点, 一个点双一定属于同一个连通块, 割点所在的所有点双中只有一个中全是连通块中点, 其他的不能是当前连通块的点, 得到结论其他的每个都是一个割点. 即被删的点集也恰好是若干完整点双.

于是建圆方树, 要求删若干方点使得剩下的圆点构成连通块, 连通块大小满足限制.

发现重心一定会被删, 考虑如果不删重心一定有一棵子树大于一半, 所以以它为根, 这样每个连通块都是一个子树, 这就很好.

于是对于 $k=0$, 枚举子树大小 $s$, 对当前 $u$ 的某个儿子子树 $\ge s$ 一定要删, 儿子子树小于 $s$ 则一定不能删, 方案唯一.

对 $k=1$ 枚举子树大小 $s, s+1$, 同理有 $<s$ 一定不删 $>s$ 一定删, 但如果 $=s$ 可以留着让连通块大小是 $t+1$, 只能留一个, 枚举留哪个等于 $s$ 的儿子剩下的也都要删.

现在单次复杂度线性, $k=0$ 复杂度 $nd(n)$, $k=1$ 复杂度 $n\sqrt n$.

todo

P8571 [JRKSJ R6] Dedicatus545

AC机可以 $O(\vert s\vert+\sum \vert t\vert)$ 的算匹配, 具体的, 不断跳转移边, 则当前点parent tree上祖先中的终止节点都会被匹配.

长于根号的串直接每个跑一遍匹配+建线段树

短于根号的串, ac机上会标 $\sqrt n$ 个节点, 相当于 $\sqrt n$ 个询问到根的链上编号在 $[l, r]$ 的终止节点个数, 那么再转到dfs序上, 就是矩形加单点和, 用 $O(\sqrt n)-O(1)$ 的分块秒了.

然后这个复杂度看起来很爆炸? 但设块长为 $B$, 其实是平衡 $\dfrac{l}{B}n+qB$, 平均起来2e5的样子.