其实是清华营 2024 预选赛的 K. String Mutation

题意大概是说给一个字符串，有三个操作：

  1. 某个位置变成某个字符。
  2. 所有等于 $x$ 的位置全部变成 $y$ 。
  3. 查询两个子串是否一样。

做法很简单，就是启发式合并然后用数据结构维护一下 Hash 值。

但是我用的线段树，后面和朋友交流发现可以用树状数组，这个玩意能求逆确实可以用树状数组，唐了。

然后呢，我本能的认为这玩意的复杂度应该是一个启发式合并 + 修改字符的复杂度，所以时间复杂度应该是 $O(n\log^2{n} + q\log{n})$ 。

但出乎意料的事情来了，首先，朋友告诉我，启发式合并的时间复杂度应该是 $\log{26}$ ，我一想还真是。

设计函数 $f(n,k)$ 表示集合大小为 $n$ ，合并了 $k$ 次的复杂度，那么有：

PS：下面的所有 $\log$ 全是以 $2$ 为底。

$f(n,0)\le n\log{(0+1)}$ ，现在归纳证明：$f(n,k)\le n\log{k+1}$ 。

假设合并的集合为 $x\le y,t\le t-1,k-t$ 。

那么有：$f(n,k)\le x\log{t}+y\log{k-t+1}+x$ ，只需证明右边 $\le n\log{k+1}$ 即可。

如果 $2t\le k+1$ 即 $2t-1\le k$，那么显然有 $x\log{t}\le x\log{k+1}-x$ 。

如果 $2(k-t+1)\le k+1$ ，即 $k\le 2t-1$ ，那么显然有 $y\log{k-t}\ke y\log{n}-y\le y\log{n} - x$ 。

而显然这两种情况必定发生一种。

综上归纳成立。

就在我以为这就结束的时候，我打算写下这篇博客，但是我想着干脆把给原题写个完整的证明吧。

意外发生了，原来后面不是 $q\log$ 的，是 $q\log^2$ 的。

一个简单的构造方法：

假设字符集无穷，一开始有 $n$ 个集合就可以达到 $n\log^{n}$ 。

如果一开始没有 $n$ 个集合，那么在用了 $S$ 次操作后，变出大小为 $n$ 的集合，然后用操作 $1$ 变出 $n$ 个集合。（$S$ 是初始的不同字符个数）

但是如果字符集不是无穷呢？也简单，调整一下操作的顺序就可以做到了，简单来说，类似二进制那样，现在有 $2^k$ 大小的集合，其中不同集合 $k$ 不同，然后每次让大集合吐出一个大小为 $1$ 的集合，然后从小到大把相同大小的集合合并即可。

可以注意到，这个过程实际上是把类似线段树一样的合并过程给全部完整的走了一遍的，所以时间复杂度是：$O(n\log^2{n})$ 的，而且付出的操作是 $O(n)$ 的，所以总的时间复杂度至少是 $O(q\log^2{n})$ 的。

而证明是这个复杂度也不难，一开始生成 $q$ 个大小为 $1$ 的集合，然后把操作 $1$ 看成合并。

这样时间复杂度是：$q\log^2{(n+q)}$ 的，欸，和 $q\log^2{n}$ 还有区别，那要怎么消除这个区别呢？

很简单，每隔 $n$ 次看一眼就行了，具体来说，将操作 $n$ 次分成一组，这样每 $n$ 组的时间复杂度按照上述证明，上界为 $\log^2{n}$ 的，所以总的时间复杂度是 $q\log^2{n}$ 的，证毕。

所以最终的时间复杂度是：$O(n\log{26}\log{n}+q\log^2{n})$ 的。

真是太 amazing 了。