Borůvka 算法

定义 $E’$ 为我们当前找到的最小生成森林的边。在算法执行过程中，我们逐步向 $E’$ 加边，定义 连通块 表示一个点集 $V’\subseteq V$ ，且这个点集中的任意两个点 $u$ , $v$ 在 $E’$ 中的边构成的子图上是连通的（互相可达）。

定义一个连通块的 最小边 为它连向其它连通块的边中权值最小的那一条。

初始时， $E’=\varnothing$ ，每个点各自是一个连通块：

1. 计算每个点分别属于哪个连通块。将每个连通块都设为“没有最小边”。
2. 遍历每条边 $(u, v)$ ，如果 $u$ 和 $v$ 不在同一个连通块，就用这条边的边权分别更新 $u$ 和 $v$ 所在连通块的最小边。
3. 如果所有连通块都没有最小边，退出程序，此时的 $E’$ 就是原图最小生成森林的边集。否则，将每个有最小边的连通块的最小边加入 $E’$ ，返回第一步。

当原图连通时，每次迭代连通块数量至少减半，算法只会迭代不超过 $O(\log V)$ 次，而原图不连通时相当于多个子问题，因此算法复杂度是 $O(E\log V)$ 的。给出算法的伪代码：（修改自 维基百科 ）

$$\begin{array}{ll} 1 & \textbf{Input. } \text{A graph }G\text{ whose edges have distinct weights. } \\ 2 & \textbf{Output. } \text{The minimum spanning forest of }G . \\ 3 & \textbf{Method. } \\ 4 & \text{Initialize a forest }F\text{ to be a set of one-vertex trees} \\ 5 & \textbf{while } \text{True} \\ 6 & \qquad \text{Find the components of }F\text{ and label each vertex of }G\text{ by its component } \\ 7 & \qquad \text{Initialize the cheapest edge for each component to "None"} \\ 8 & \qquad \textbf{for } \text{each edge }(u, v)\text{ of }G \\ 9 & \qquad\qquad \textbf{if } u\text{ and }v\text{ have different component labels} \\ 10 & \qquad\qquad\qquad \textbf{if } (u, v)\text{ is cheaper than the cheapest edge for the component of }u \\ 11 & \qquad\qquad\qquad\qquad\text{ Set }(u, v)\text{ as the cheapest edge for the component of }u \\ 12 & \qquad\qquad\qquad \textbf{if } (u, v)\text{ is cheaper than the cheapest edge for the component of }v \\ 13 & \qquad\qquad\qquad\qquad\text{ Set }(u, v)\text{ as the cheapest edge for the component of }v \\ 14 & \qquad \textbf{if }\text{ all components'cheapest edges are "None"} \\ 15 & \qquad\qquad \textbf{return } F \\ 16 & \qquad \textbf{for }\text{ each component whose cheapest edge is not "None"} \\ 17 & \qquad\qquad\text{ Add its cheapest edge to }F \\ \end{array}$$

转载自 最小生成树 - OI Wiki

题面

定义 half border 为长度不超过一半的 border。

给定一个长度为 $n$ 的字符串 $s$，$q$ 次询问，每次独立地删除一个子串 $[l_i,r_i]$，左右连起来，询问这个串的 half border 长度和。

其中 $1 \le n, q \le 5 \cdot 10^5$。

分析

不妨设左半边比右半边长。

有两部分贡献：

1. border 不跨过边界，这部分就是原串长度小于 $\min(l_i, n-r_i+1)$ 的 border 之和，预处理后二分即可。

2. border 跨过边界了边界，下面分析这部分如何计算。

观察到，实际上是前缀的 border 位置和后缀的 border 位置求了交。

对前缀和后缀分别建立 KMP 的 fail 树。询问离线到前缀树上的每个点。

设有询问 $[1, l_i]$ 和 $[r_i, n]$，在前缀树上根到 $l_i$ 的所有点，若其出现在后缀树上 $r_i$ 的子树内，则其会被算一次长度的贡献。

但是，上面没有考虑到 half border 的长度限制，设路径上的一个点 $k$，$2(k+n-r_i+1) \le l_i+n-r_i+1$，也就是 $k$ 小于某个值。对于这个限制，在路径上二分，把询问二次离线到对应的点，使用树状数组容易计算答案。

徐州 D Rikka with Subsequences

UpSolved by XLor.

求每种本质不同好子序列的出现次数立方和。

令 $f(a)$ 表示子序列 $a$ 的出现次数，立方和展开一下，$\sum_{i=1}^{f(a)} \sum_{j=1}^{f(a)} \sum_{k=1}^{f(a)} 1$。观察上式的实际意义，等价于将序列复制三份，求公共好子序列的个数。举例来说，假如 $a$ 作为子序列出现了 $2$ 次，分别出现在位置序列 $a_1,a_2$，那么有公共子序列 $(a_1,a_1,a_1)$ 一直到 $(a_2,a_2,a_2)$ 共 $8$ 种对应。

记 $dp(i,j,k)$ 表示在第一个串以 $i$ 结尾，第二个 $j$ 结尾，第三个 $k$ 结尾的方案数。$dp(i,j,k)$ 有值当且仅当 $a_i=a_j=a_k$。

$$dp(i,j,k)=[ a_i=a_j=a_k ]( \sum_{i'=1}^{i-1} \sum_{j'=1}^{j-1} \sum_{k'=1}^{k-1} dp(i',j',k') [M(a_{j'},a_i)] )$$

转移过程相当于同时从 $(i’,j’,k’)$ 走到 $(i,j,k)$，我们将这个过程拆开变成 $3$ 个阶段，钦定先走 $i$，再走 $k$，最后走 $j$。也就是说最后一步的 $j’$ 和 $i$ 两个之间必须可以走。

枚举 $i$，令 $f(i,j,k) = \sum_{i’=1}^{i=1} dp(i’,j,k)$, $g(i,j,k) = f(i,j,k) [M(a_j, a_i)]$。

$$dp(i,j,k)=[ a_i=a_j=a_k ] ( \sum_{j'=1}^{j-1} \sum_{k'=1}^{k-1} \sum_{i'=1}^{i=1} dp(i',j',k') [M(a_{j'}, a_i)]) \\ dp(i,j,k)=[ a_i=a_j=a_k ] ( \sum_{j'=1}^{j-1} \sum_{k'=1}^{k-1} g(i,j',k')) \\$$

因此，$dp$ 的转移，只需要对 $g$ 数组做一次二维前缀和即可。

徐州 F Rikka with Nice Counting Striking Back

UpSolved by XLor

求母串的本质不同子串个数，且子串 $T$ 满足，对于任意非空串 $P$，若 $TP=PT$，那么 $TP$ 不是 $S$ 的子串。

观察一下，对于子串 $T$，当存在 $TT$，$T$ 不合法，存在 $TTT$，$TT$ 不合法，也就是对于这样的一组串只会算一次。

上述等价于，减去多算的 $TT,TTT,TTTT,\dots$，暴力枚举每个 Runs 内部的每个右端点的周期串，哈希去重。

徐州 G Rikka with Intersections of Paths

UpSolved by XLor

给定树上 $q$ 条路径，求选出 $k$ 条有公共点的路径的方案数。

对于一种选择方案，公共点数减去公共边数等于 $1$。

对于所有点和边，分别求其出现在多少条路径上，相减即为答案。

青岛 I Soldier Game

UpSolved by XLor.

给定一个序列，将序列划分为长度为 $1$ 或 $2$ 的子串，最小化每个子串和的极差。

显然，枚举最小值，dp 出可能的最小的最大值。

令 $\infty$ 表示情况不存在，$-\infty$ 表示任意。

记 $dp(i,0/1)$ 表示 $i$ 位置是否被用过的最小最大值，当前下界为 $D$。

$$dp(i,0)=dp(i-1,1) \\ dp(i,1)=\min(\max(a_i+a_{i-1}, dp(i-1,0)), \max(a_i, dp(i-1,1)))$$

上式中的 $a_i,a_i+a_{i-1}$ 均会在 $< D$ 时，被换成 $\infty$。最终最小的最大值为 $dp(n,1)$。

上面的 $dp$ 状态改成可以线段树动态维护的，允许区间合并的状态。

令 $dp(l,r,0/1,0/1)$ 表示：

• 00：$[l,r]$ 都被用上；

• 01：$l$ 和 $l-1$ 配对；

• 10：$r$ 没有被用上；

• 11：$l$ 和 $l-1$ 配对，且 $r$ 没有被用上。

合并时，只需要枚举中间两个位置的情况即可。

Day 2

D 卡拉巴什的字符串

定义一个串的 LCP 集合，由每对后缀的 LCP 值组成。

给定一个母串，求它的每个前缀的这个集合的 mex。

考虑一个 endpos 等价类，如果它的出现位置不止一个，考虑某两个出现位置，它们的 LCP 为 $1$（必定存在，因为不存在的话与等价类定义不符），同时往左走一步，LCP 变成 $2$，一直到最大长度，都会出现。

因此答案必定是这样的结点的最大长度 $+1$。考虑这样的结点一定不是叶子结点，一定是一个内部结点，且根据后缀树的结构，内部不存在二度结点，因此只需要对所有内部节点取 $\max$ 即可。

注意特判：单字符集串，没有 $0$。

K 破忒头的匿名信

给定至多 $5 \cdot 10^5$ 个长度总和至多 $5 \cdot 10^5$ 的模板串，每个模板串有花费 $cost_i$。

要求将母串分为数段，每段均为模板串，产生的代价是该串的花费。

暴力：建出 AC 自动机，母串在 AC 自动机上跑，每次暴力跳 fail 指针转移 dp。

优化：暴力跳 fail 可能会退化为 $O(n^2)$，注意到几个事实：串长的种类小于 $\sqrt{5 \cdot 10^5}$，而每次跳 fail 串长至少减一，因此扣出有效的转移即可。

Day 3

J 简单字符串

定义 $f(S,k)$ 表示将字符串 $S$ 划分为至多 $k$ 段，对于所有划分方案，要求最小化这种划分的字典序最大串。

每次询问一个后缀 $S[l \dots |S|]$，划分为至多 $k$ 段的答案，若有多种答案，输出左端点最小的，且它必须在某一种划分中。

大胆猜测：一定切在后缀的 Lyndon 分解上。

求出每个后缀的 Lyndon 分解，记这个 Lyndon 分解长度为 $p$，和这个 $$ 在后面一共重复了 $cnt$ 次，开始讨论：

1. 后缀有一个整周期为 Lyndon 分解的长度，即类似 bbbbbb，我们肯定是尽量平均的划分，并且为了左端点最小，也就是取后缀的某几个周期的前缀。

2. $cnt$ 次 $p$ 后还有 Lyndon 分解，即类似 bbbba，如果 $cnt \bmod k = 0$，我们将 $cnt$ 次 $p$ 平均分解，答案为划分后最后一个段。

3. 同情况 $2$，$cnt \bmod k \neq 0$，当成 $cnt + 1$ 段平均分解，答案为该后缀的前缀。

关于后两种情况的区别，如果整除的话，只将重复的 $cnt$ 段平均分解，那么答案就是最后一段，若你移动之前的某个分解位置，产生的字符串会大于这个最后一段（根据 Lyndon 分解）。其他情况就正常对所有段均分，取前缀即可。

E Fedya the Potter Strikes Back

强制在线，维护一个串和一个数组，每次向后加一个字母和一个值，定义一个子串的权值为数组对应区间的最小值，求出所有和串的子串，满足等于相应长度的前缀条件，价值之和。

显然，只需要算出每次 push back 产生的贡献即可。

首先，可以动态维护一下每个前缀的 border 集合，遍历一遍得到答案，但是 border 集合的总大小可能是 $O(n^2)$ 的。因此，我们可以考虑维护 border 集合的变化，显然这部分是均摊 $O(n)$ 的（参考 KMP 算法证明）。

考虑 KMP 的过程，从上一点的 fail，暴力往上跳找到第一个点，其对应前缀的下一个字母等于当前字母，显然上跳的中间过程，这些前一次的 border 无法扩展，需要从 border 集合中被删除。

但是，这部分是不够的。还需要考虑，当前的最长 border 之前的转移情况，实际上等同于这个 border 作为前缀时的转移情况，将其丢进被删除集合即可。

官方题解这里给出了另外一个做法，多维护一个上跳指针，表示往上第一个后继字母与当前不同的点，每次暴力往上跳即可（次数等价于变化大小）。

最后，考虑如何维护出答案的增量。加入新的 border，删除 border，border 集合保留未删除的部分，相当于每个权值对于新加入元素对于 $w$ 取 $\min$。使用 std::map 维护每种取值的个数，取 $\min$ 就暴力枚举比 $w$ 大的元素。这样复杂度是均摊 $O(n \log n)$ 的，因为如果我们对同一个 std::map 取 $\min$，其大小（种类数）不会增加，而操作代价实质是大小的变化量。

A New Year Garland

B Verse For Santa

读错题了。

C Stack of Presents

D Santa’s Bot

E New Year Permutations

定义一个长度为 $n$ 的排列合法，当且仅当，满足：排列可以划分成一系列连续的子区间，每个子区间是一个周期等于子区间长度的置换群，且子区间的第一个位置是该子区间的最大值。求长度为 $n$ 的字典序第 $k$ 大的合法排列。

首先，dp 出每个点开头有多个合法排列，即枚举这个点开始的子区间长度，长度为 $n$ 的合法置换群有 $(n-2)!$ 种。

然后，开始逐位确定，枚举当前位置应该填多少，等价于子区间的结束位置，直到方案数大于 $k$，说明子区间在这里结束。

这里需要生成字典序第 $k$ 的一个置换群，这里的 $k$ 等于全局的 $k$ 除掉后面的方案数（每种子区间排列对应后面的排列），全局的 $k$ 取模。

最后，问题就是解决生成这样的置换群，还是考虑逐位确定，使用并查集检查防止提前出现环，方案数使用 $(n-2)!$ 进行更新。

注意一些细节：

• 使用 C++ 防止爆 $long long$，自定义一个带上限的加法和乘法；

• 注意 break；

• 字典序编号为 $0$ 到总方案数减一。

F New Year and Handle Change

wqs 二分。

榜单

A Shuffle Hashing

给定一个串 $s$，随机打乱顺序后，询问是否可能是 $t$ 的子串。

暴力枚举 $t$ 的每个子串。

B A and B

智商没对上 T^T。

给定两个整数 $a,b$，第 $i$ 轮选一个数加 $i$，最小多少轮两数相同。

相当于将 $1,2,\dots,n$ 分配到两个数组中，一个和为 $s$ 另一个和为 $t$，且 $s+t=n(n+1)/2,s-t=|a-b|$。

C Berry Jam

D Segment Tree

给定 $n$ 条线段，两条线段之间连边当且仅当相交不包含，端点为 $1$ 到 $2n$ 的排列。

扫描线，枚举所有与给线段相交不包含的部分，并查集合并，如果出现环则停止。最多暴力合并 $n$ 次。

最后检查一下并查集完全联通。

E Tests for problem D

给定一张图，生成一下 D 题的线段。

递归地进行构造，对于子树 $u$，他的左端点为 $l_u$，右端点位置是 $r_u+deg_u+1$（$l_u,r_u$ 为递归参数）。

对于他的所有儿子结点，都与 $u$ 线段相交，并且兄弟结点依次包含，左端点会从右边 $r_u+deg_u$ 一直放到 $r_u+1$。

考虑右端点的限制，因为需要包含前面的兄弟的子树内结点，因此右端点需要往右偏移一段，即上一个兄弟的子树大小的两倍减一（减一由于根节点的左端点在 $u$ 的内部，$u$ 外部的点数为两倍减一）。

初始时，$l_1=r_1=1$。

F Cards

随机变量 $X$ 服从 $B(n,p)$，求 $E(X^k)$。

根据斯特林数展开

$$E[X^k]=\sum_{i=0}^k S(k,i) E[X(X-1)\dots (X-i+1)]$$

伯努利分布的 $i$ 次下降幂

$$E[X(X-1)\dots (X-i+1)]=A(n,i)p^i$$

带入得到答案。

参考资料：Factorial_moment 和 What is the kth factorial moment of the binomial distribution?。

考虑直接推式子，实际上等价于上面下降幂的推导过程

$$E(X^k)=\sum_{i=0}^n {n \choose i} \frac{1}{m}^i(1-\frac{1}{m})^{n-i} i^k \\ =\sum_{j=0}^{k} S(k,j) \sum_{i=0}^n {n \choose i} \frac{1}{m}^i(1-\frac{1}{m})^{n-i} A(i,j)$$

题意

有一排长度为 $n$ 空白序列，有 $q$ 个时刻，每个时刻会将序列中的某一个位置填上数字 $h_i$，或者询问序列 $[l,r]$ 区间中与 $h$ 差的绝对值的最小值。

其中 $1 \le n \le 5 \cdot 10^5, 1 \le q \le 10^6$。

分析

有一个显然的做法，转化为四维偏序问题，时间复杂度 $O(q\log^3q)$，显然 T 飞了。

将询问离线，从左到右枚举右端点 $r$，如果位置 $r$ 曾经出现，则将 $r$ 插入数据结构，枚举这个点结束的询问进行回答。

令位置 $i$ 的出现时间为 $appear(i)$，对于询问 $(t,l,r,h)$，其中 $l,r,h$ 为输入，$t$ 为时间戳，我们需要在数据结构中查询权值小于等于 $h$ 的最大位置 $pos$，满足 $pos \ge l$ 且 $appear(pos) < t$，或者权值大于等于 $h$ 的最小位置，满足同样的条件。

为此，我们维护一棵权值线段树。

记权值线段树上的结点 $u$ 对应区间 $[l,r]$，在 $u$ 上维护出权值在 $[l,r]$ 范围内的所有位置。

查询时，如果 $[l,r]$ 包含于询问的值域区间，则检查当前区间内是否存在一个位置满足上述条件，如果满足则继续往下递归，直到叶子，否则剪枝。显然，如果一个区间不含合法点，会直接被剪枝，因此实际经过的结点仍然只有 $\log n$ 个。

但是，上述做法时间仍然难以接受，因为每个结点内需要使用一个数据结构进行维护，时间复杂度为 $O((n+q)\log^2n)$。

继续对其进行优化，我们注意到一个事实，在一个线段树结点内，如果 $i < j$ 且 $appear(i)>appear(j)$，那么 $i$ 一定不如 $j$ 优，因为 $j$ 更靠近右端点，出现时间也更加早。

因为我们可以直接线段树结点上，维护一个关于出现时间递增的单调栈，因为最多只有 $n\log n$ 个结点，因此插入的时间复杂度是 $O(n \log n)$。查询时，在该单调栈上二分一个位置 $pos$，使得 $pos \ge l$ 且 $appear(pos) < t$。

最终，时间复杂度为 $O(n\log q + q \log^2q)$。