题解：P14363 [CSP-S 2025] 谐音替换 / replace（民间数据）

wlight · 2025-11-02 11:53:22 · 题解

前置知识

Trie字典树 树上差分 树状数组 扫描线思想

题目分析

题目给定 n 个字符串对 (s_{i,1},s_{i,2})，保证每对字符串长度相等。再给出 q 次询问，每次询问给定字符串对 (t_{j,1},t_{j,2})，问有多少个 (s_{i,1},s_{i,2}) 可以把 t_{j,1} 替换成 t_{j,2}.

首先让我们分析一下替换操作。

有以下性质：

1. 替换后，字符串的长度不变。
2. 替换后，原字符串（t_{j,1}）与新字符串（t_{j,2}）的最短不同区间的字符与替换操作使用的字符串对（(s_{i,1},s_{i,2})）的最短不同区间的字符相同。

::::info[最短不同区间] 若将一对字符串的区间中的字符都删去后，字符串对相同，则记这个区间为不同区间，在所有的不同区间中的最短的那个，就记作最短不同区间。

例如：

代码

:::success[代码]

#include<bits/stdc++.h>
using namespace std;
namespace SOLVE{
#define N 200000
#define LEN 5000000
#define PII pair<int,int>
#define fi first
#define se second
int n,q;
char tmp[LEN+N*2+2],tmp2[LEN+N*2+2];
char *s1[N+1],*s2[N+1],*t1[N+1],*t2[N+1];
inline void input(){
    scanf("%d%d",&n,&q);
    int tpsz=1,tp2sz=1;
    int L1=0,L2=0;
    for(int i=1,len;i<=n;++i){
        scanf("%s",tmp+tpsz);
        len=strlen(tmp+tpsz);
        s1[i]=tmp+tpsz-1;
        tpsz+=len+1;
        L1+=len;
        scanf("%s",tmp+tpsz);
        len=strlen(tmp+tpsz);
        s2[i]=tmp+tpsz-1;
        tpsz+=len+1;
        L1+=len;
    }
    assert(L1<=5000000);
    for(int i=1,len;i<=q;++i){
        scanf("%s",tmp2+tp2sz);
        len=strlen(tmp2+tp2sz);
        t1[i]=tmp2+tp2sz-1;
        tp2sz+=len+1;
        L2+=len;
        scanf("%s",tmp2+tp2sz);
        len=strlen(tmp2+tp2sz);
        t2[i]=tmp2+tp2sz-1;
        tp2sz+=len+1;
        L2+=len;
    }
    assert(L2<=5000000);
}
int ans[N+1],p[N+1],p2[N+1];
int trK[LEN+1][26],numK[LEN+1],totK,sumK;
int slen[N+1];
int hdL[N+1],hdR[N+1];
vector<int> idR[LEN+N+1];
vector<PII> ask[LEN+N+1];
int trL[LEN+N+1][26],totL;
int trR[LEN+N+1][26],totR,dfn[LEN+N+1],dfu[LEN+N+1],dfc;
int vis[LEN+N+1];
struct BIT{
    int tr[2*N+2];
    inline void add(int k,int x){for(;k<=n+q+1;k+=k&-k)tr[k]+=x;}
    inline int query(int k){int ans=0;for(;k;k-=k&-k)ans+=tr[k];return ans;}
}bit;
inline void dfsR(int u){
    if(vis[u])++dfc;
    dfn[u]=dfc;
    for(int i=0;i<26;++i)if(trR[u][i])dfsR(trR[u][i]);
    dfu[u]=dfc;
}
inline void dfsL(int u){
    for(int id:idR[u]){
        bit.add(dfn[id],1);
        bit.add(dfu[id]+1,-1);
    }
    for(auto Q:ask[u]){
        ans[Q.se]=bit.query(dfn[Q.fi]);
    }
    for(int i=0;i<26;++i)if(trL[u][i])dfsL(trL[u][i]);
    for(int id:idR[u]){
        bit.add(dfn[id],-1);
        bit.add(dfu[id]+1,1);
    }
}
inline void solve(){
    for(int i=1;i<=n;++i){
        slen[i]=strlen(s1[i]+1);
        int l=1,r=slen[i];
        while(l<=r&&s1[i][l]==s2[i][l])++l;
        if(l>r)continue;
        while(l<=r&&s1[i][r]==s2[i][r])--r;
        for(int j=l,cur=1;j<=r;++j){
            if(!trK[cur][s1[i][j]-'a'])trK[cur][s1[i][j]-'a']=++totK;
            cur=trK[cur][s1[i][j]-'a'];
            if(!trK[cur][s2[i][j]-'a'])trK[cur][s2[i][j]-'a']=++totK;
            cur=trK[cur][s2[i][j]-'a'];
            if(j==r){
                if(!numK[cur])numK[cur]=++sumK;
                p[i]=numK[cur];
            }
        }
        if(!hdL[p[i]])hdL[p[i]]=++totL;
        int Lcur=hdL[p[i]];
        for(int j=l;--j;){
            if(!trL[Lcur][s1[i][j]-'a'])trL[Lcur][s1[i][j]-'a']=++totL;
            Lcur=trL[Lcur][s1[i][j]-'a'];
        }
        if(!hdR[p[i]])hdR[p[i]]=++totR;
        int Rcur=hdR[p[i]];
        for(int j=r+1;j<=slen[i];++j){
            if(!trR[Rcur][s1[i][j]-'a'])trR[Rcur][s1[i][j]-'a']=++totR;
            Rcur=trR[Rcur][s1[i][j]-'a'];
        }
        idR[Lcur].push_back(Rcur);
        vis[Rcur]=1;
    }
    for(int i=1;i<=q;++i){
        int tlen=strlen(t1[i]+1);
        if(tlen!=strlen(t2[i]+1))continue;
        int l=1,r=tlen;
        while(l<=r&&t1[i][l]==t2[i][l])++l;
        while(l<=r&&t1[i][r]==t2[i][r])--r;
        for(int j=l,cur=1;j<=r;++j){
            cur=trK[cur][t1[i][j]-'a'];
            if(!cur)break;
            cur=trK[cur][t2[i][j]-'a'];
            if(!cur)break;
            if(j==r){
                p2[i]=numK[cur];
            }
        }
        if(!p2[i])continue;
        int Lcur=hdL[p2[i]],Rcur=hdR[p2[i]];
        for(int j=l;--j;){
            if(!trL[Lcur][t1[i][j]-'a'])break;
            Lcur=trL[Lcur][t1[i][j]-'a'];
        }
        for(int j=r+1;j<=tlen;++j){
            if(!trR[Rcur][t1[i][j]-'a'])break;
            Rcur=trR[Rcur][t1[i][j]-'a'];
        }
        vis[Rcur]=1;
        ask[Lcur].push_back({Rcur,i});
    }
    for(int i=1;i<=sumK;++i){
        dfsR(hdR[i]);
        dfsL(hdL[i]);
    }
}
inline void output(){
    for(int i=1;i<=q;++i)printf("%d\n",ans[i]);
}
void main(){
    input();
    solve();
    output();
}
}
int main(){SOLVE::main();}

:::