论如何用六级算法爆切 [CSP-S 2025] 谐音替换

· · 题解

注意到 AC 自动机和离线处理思想均为 NOI 级算法。CSP 小朋友怎么会 NOI 级算法呢？还有一篇文章提到了主席树在线做法，CSP 小朋友肯定也不会主席树。同样的，CSP 小朋友也肯定不会偏序。

下列讨论自动忽略 s_{i,1}=s_{i,2} 和 |t_{i,1}|\ne|t_{i,2}| 的情况。

一个替换 s_i 的本质是将一个子串替换为另一个子串，且这两个串没有公共前缀或者后缀。我们令 s_{i,1} 和 s_{i,2} 分别等于 x_i+y_i+z_i 和 x_i+y'_i+z_i，其中 y_i 和 y'_i 没有公共前缀或后缀。

我们不妨对于 y+y'+\text{\#}+z+\text{*}+r(x) 建立字典树，其中 r(x) 表示 x 翻转后的串。

接下来我们处理查询。一个查询的本质是要将一个子串替换为另一个子串且两个子串没有公共前缀或后缀。我们令 t_{i,1} 和 t_{i,2} 分别等于 a+b+c 和 a+b'+c。接下来我们考虑在字典树上查询。我们发现，符合要求的 s 一定满足其本质与查询串的本质相同，且 x 和 z 分别是 a 和 c 的后缀和前缀。于是我们考虑枚举 z，令当前枚举的 z 为 c'，那么只需要查询当前枚举的 z' 下，前缀满足条件的 s 的数量就可以了。

我们在每一个 y+y'+\text{\#}+z+\text{*} 对应节点的子树内，做一个树上前缀和，记录这个子树的根节点到每个节点的链上有多少个 s，那么我们要查询的就是 b+b'+\text{\#}+c'+\text{*}+r(a) 节点上存的值。我们发现，可以使用 std::unordered_map 存储哈希值对应的节点上的值，即可 O(1) 查询。现在只剩下了一个问题，即可能并不存在这样的节点。于是我们可以二分最长的存在 b+b'+\text{\#}+c'+\text{*}+r(a') 节点的 a 的后缀 a'，复杂度 O(\log L)。这样我们就解决了整个问题。

在实现的时候，不加入字符 \text{*} 也可以。总复杂度 O(L\log L)。

代码（赛后重写）：

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int P = 1e9+7, Q=1e9+9, B=457, C=997;
ll next_hash (ll prev, int chr)
{
    ll a = prev >> 32, b = prev & -1u; chr ++;
    a = (a * B + chr) % P;
    b = (b * C + chr) % Q;
    return (a << 32) | b;
}
const int maxl = 5002424;
const int maxn = 200083;
struct node
{ int pt, nxt [27]; }
trie [maxl*2+maxn];
struct pn
{
    int rt;
    unordered_map <ll, int> mp;
} pns [maxn];
int ctc, ptc;
char s [maxl], t [maxl];
void q_diff (int len, int& dnq, int& dxq)
{
    int nq = len+1, xq=-1;
    int i;
    for (i=0; i<len; i++)
    if (s [i] != t [i])
    nq = min (nq, i), xq = max (xq, i);
    dnq = nq; dxq = xq;
}
#define jnode(var,chr) if(trie[var].nxt[chr])var=trie[var].nxt[chr];else var=trie[var].nxt[chr]=++ctc
#define ord(ch) (ch=='#'?26:ch-'a')
void add_s (int idx)
{
    scanf ("%s%s", s, t);
    int len = strlen (s);
    if (strcmp (s, t) == 0) return;
    int nq, xq; q_diff (len, nq, xq);
    int i, cur = 0;
    for (i=nq; i<=xq; i++)
    {
        jnode (cur, ord (s [i]));
        jnode (cur, ord (t [i]));
    }
    jnode (cur, 26);
    for (; i<len; i++)
    jnode (cur, ord (s [i]));
    int pt = trie [cur] .pt;
    if (pt == 0) pt = trie [cur] .pt = ++ptc;
    cur = pns [pt] .rt;
    if (cur == 0) cur = pns [pt] .rt = ++ctc;
    for (i=nq-1; i>=0; i--)
    jnode (cur, ord (s [i]));
    trie [cur] .pt ++;
}
void dfs_pn (int rt, int cur, ll ch, int cn)
{
    pns [rt] .mp [ch] = cn = trie [cur] .pt += cn;
    int i, m;
    for (i=0; i<27; i++)
    if (m = trie [cur] .nxt [i])
    dfs_pn (rt, m, next_hash (ch, i), cn);
}
ll hashes [maxl];
int query (void)
{
    scanf ("%s%s", s, t);
    int len = strlen (s);
    if (strlen (t) != len) return 0;
    int nq, xq; q_diff (len, nq, xq);
    int i, cur = 0;
    for (i=1; i<=nq; i++) hashes [i] = next_hash (hashes [i-1], ord (s [nq-i]));
    for (i=nq; i<=xq; i++)
    {
        if (0 == (cur = trie [cur] .nxt [ord (s [i])])) return 0;
        if (0 == (cur = trie [cur] .nxt [ord (t [i])])) return 0;
    }
    if (0 == (cur = trie [cur] .nxt [26])) return 0;
    int ans = 0;
    for (i=xq; i<len; i++)
    {
        if (trie [cur] .pt != 0)
        {
            int l = 0, r = nq;
            pn& cpn = pns [trie [cur] .pt];
            while (l < r)
            {
                int m = l+r+1 >> 1;
                if (cpn.mp.count (hashes [m])) l = m;
                else r = m-1;
            }
            ans += cpn.mp [hashes [l]];
        }
        if (i != len-1)
        if (0 == (cur = trie [cur] .nxt [ord (t [i+1])]))
        break;
    }
    return ans;
}
int main (void)
{
    int n, q; scanf ("%d%d", &n, &q);
    int i; for (i=1; i<=n; i++) add_s (i);
    for (i=1; i<=ptc; i++) dfs_pn (i, pns [i] .rt, 0, 0);
    for (i=1; i<=q; i++) printf ("%d\n", query ());
}

考场上两个小时都没调出来，刚刚重写十分钟就过了。每次遇到树相关的题都是这样，我是不是被诅咒了。

题解都是离线或 AC 自动机，怎么可以这样。