SP3109 题解

· · 题解

SP3109

前言

双倍经验

这题怎么也调了我三天啊 qwq，什么时候代码能力才能强起来啊……

本题解是一篇块状链表的题解，平衡树党请跳过……

注意，笔者的块状链表也是自学，本题想法也是自己想出来的，有诸多不足，为防止误人子弟，请在评论区告知！

解法分析

其实用块链还是很容易想到的吧\kk

先考虑没有插入修改怎么做，就是裸的 hash，因为字符串匹配肯定越长越难，所以具有单调性，可以二分。

然后……加入丧心病狂的插入修改操作……

所以需要动态维护 hash 值，这可合并，用数据结构即可。

你当然可以用平衡树，但是代码思路简单粗暴的块状链表明显更有优越性。

首先简单介绍一下块状链表，可以见这里。

以我的话说，大致是一种链表套数组的结构，通过分裂合并来保证复杂度。

反正只要记住有了这玩意儿我们就可以进行插入修改操作了。

实现

具体来说，我们将字符串转换为数字，分成 \sqrt n 个块，预处理出每个块的 hash 值、这个块前面的数字个数和这个块的前缀 hash 值。

对于插入，暴力平移数组，直接插入，然后重新维护信息，复杂度 O(\sqrt n)。

对于修改，暴力改数组，然后重新算块内信息，复杂度 O(\sqrt n)。

对于查询，就有点难搞了。我一开始的思路是直接二分长度，转判定性问题以后，求区间 hash。其实拆为两边散块和中间整块后，结合已知信息求解就可以了。但是找到端点位置是 O(\sqrt n) 的，所以总时间复杂度是 O(\sqrt n \times \log n) 的。完全没有体现出块状链表的优越性！！

于是我们想要优化（注意，接下来的内容都是笔者口胡，可能有误）。我们注意到，查询的瓶颈在于要反复找端点的位置，重复遍历了多次。可不可以不重新跳呢？注意我们预处理了每个块前数的个数，我们记录下每次块的位置，下一次直接判自己该往哪边移动。直觉告诉我们，这样移动的幅度不会太大。

我们考虑证明。因为二分的两次端点距离都会变成上一次的一半，最后端点的总移动距离就是 O(len)，其中 len 指查询区间长度。把它压缩到块上，便是最坏 O(\sqrt n) 的时间复杂度。这样查询操作的复杂度便成了 O(\sqrt n + \log n)。优越性就有了。

综合下来，我们便有了修改查询都是稳定 O(\sqrt n) 的块状链表的做法。

代码

还是比较好打的。注意链表的操作不要出错就可以了。由于块状链表的特殊性，甚至多测不需要清空。

因为是自学的，写法可能很奇怪 qwq。

代码

后记

欢迎 hack！