P9482 [NOI2023] 字符串-Solution

· · 题解

题目链接

省流：没进弱省省队的场外选手的乱胡。

题目限制比较奇怪，考虑放宽限制。

我们不妨将比较 s[i : i + l - 1] 和 R(s[i + l, i + 2l - 1]) 看作比较 s[i : n] 和 R(s[1 : i + 2l - 1])。

此时我们只可能多算贡献，因为如果前者不等于后者，那么在比较到第 l 个位置之前时已经比较好了。

因此我们只可能在前 l 位上是相同的，之后的位上出现了前者对应位小于后者的情况，进而多算答案。

我们先考虑放宽限制后的答案。

这个答案是好维护的，我们将原串和反串接在一起，中间一个特殊字符隔开，后缀排序一下。

设 rk_i 为第 i 个后缀的排名。每个子询问 i,l 合法必然满足 rk_i < rk_{2n-i-2l+2} \wedge l < r + 1，这显然是一个二维数点，离线然后用棵树状数组维护即可，鉴定为普及板子。

现在我们考虑一下可能多算的地方。因为我们已经知道 s[i : i + l - 1] = R(s[i + l, i + 2l - 1]) 了，所以 s[i : i + 2l - 1] 是一个长度为偶数的回文串。跳过它，我们要计算 s[i + 2l : n] < R(s[1 : i - 1]) 的个数，这些就是我们多算的答案。也即，满足 s[i : i + 2l - 1] 是偶回文串且 s[i + 2l : n] < R(s[1 : i - 1]) 的 i,l 个数。

一个核心观察是因为 s[i : i + 2l - 1] 是回文串，所以要么 s[i - 1] \ne s[i + 2l]，要么 s[i : i + 2l - 1] 不是当前的极长回文串，否则我们可以给两边同时加上相同的字符，回文串更长。

所以我们可以跑一个 manacher 来求出包含 s[i : i + 2l - 1] 的极长回文串。

将这个极长回文串半径值设为 c，回文中心设为 o。求出极长回文串 s[o - c + 1 : o + c] 后，我们可以直接断言，s[i + l + 2 : o + c + 1] = R(s[o - c : i - l - 1])，这是因为回文串最基础的性质——对称性。也就是说，比较 s_{o + c + 2} 和 s_{o - c - 1} 的大小即可直接判断 s[i + 2l : n] 是否小于 R(s[1 : i - 1])。

如果它没有小于 R(s[1 : i - 1])，很显然我们不会算重，直接跳。

否则，考虑 i 位置上算重了多少，我们发现如果它小于 R(s[1 : i - 1])，那么所有以 o 为回文中心的回文串都会算重。

于是对于每个会算重的极大回文串我们要减去满足 i \le o \le r \le o + c - 1 的询问个数，由于是极大回文串这必然是不重不漏的，显然也是一个二维数点，直接做就行了。

时间复杂度 \Theta(Tn\log n)，由于代码比较巨大难写而且写题解的时候还在咕，就把代码放进剪切板里了。

在之后可能会放上去的代码