题解：P14363 [CSP-S 2025] 谐音替换 / replace（暂无数据）
刚下场想了一个晚上，然后就想出了一个能过熨斗的做法。
先把
对于第一条限制，我们可以对字符串对做字符串哈希并把所有本质相同的字符串对放在一起。
对于第二条限制，可以先把
对于第三条限制也是类似的处理，只不过不用翻转字符串。这样我们就能把操作
如下给出赛后补题代码，在熨斗 S 自测中可以 AC。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define N 5000010
#define M 200010
#define INF 0x3f3f3f3f
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define pss pair<string,string>
#define cpx complex<double>
#define poly vector<ll>
#define x1 wvhrunnvt547vn834vn5
#define y1 hv23v723vn8tvn2wwwrf
#define x2 qrvr32vny3v78n4v84n4
#define y2 afuvirv7g4nb85nvn28v
mt19937_64 gen(504814527);
string ps[M],ns[M],pt[M],nt[M];ull be[M],ae[M],mpa[26],mpb[26],base_a,base_b;
struct op{string n1,n2;};struct qry{string n1,n2;int idx;};
struct point{int x,y,v;}va[M<<1],vb[M];bool cmp(point n1,point n2){return n1.x < n2.x;}
vector<op> vop[M<<2];vector<qry> vqry[M<<1];
ull b1[M<<1];int lb1,b[M*3],lb,c[N],tmp_a[N],tmp_b[N];
void add(int x,int k){
// printf("add x = %d k = %d\n",x,k);
for(;x <= lb+1;x += lowbit(x))c[x] += k;
}
int query(int x){int res = 0;for(;x;x ^= lowbit(x))res += c[x];return res;}
int ans[M],n,q,lva,lvb;
namespace trie{int lqn = 1,dfc;
struct node{int mp[26],dfn,lv;}tree[N];
int new_node(){++lqn;for(int i = 0;i < 26;++i)tree[lqn].mp[i] = 0;tree[lqn].dfn = tree[lqn].lv = 0;return lqn;}
void clear(){dfc = lqn = 0;new_node();}
void dfs(int x){tree[x].dfn = ++dfc;for(int i = 0;i < 26;++i)if(tree[x].mp[i])dfs(tree[x].mp[i]);tree[x].lv = dfc;}
int insert(string s){int pos = 1;
// printf("%s ----\n",s.c_str());
for(int i = 0;i < s.size();++i){s[i] -= 'a';
// printf("s = %d pos = %d\n",s[i],pos);
if(!tree[pos].mp[s[i]])tree[pos].mp[s[i]] = new_node();
pos = tree[pos].mp[s[i]];
}
return pos;
}
}using namespace trie;
int x1[M],x2[M],y1[M],y2[M];
// 主函数
int main(){
freopen("replace.in","r",stdin),freopen("replace.out","w",stdout);
base_a = gen(),base_b = gen();
for(int i = 0;i < 26;++i)mpa[i] = gen(),mpb[i] = gen();
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> q;
for(int i = 1;i <= n;++i){string s1,s2;cin >> s1 >> s2;if(s1 == s2)continue;// 不可能产生贡献
int fa = 0,ga = s1.size()-1;ull hash_ans = 0,bas1 = 1,bas2 = 1;
while(s1[fa] == s2[fa])++fa;while(s1[ga] == s2[ga])--ga;
// printf("such:");
for(int j = fa;j <= ga;++j){
// printf("%c",s1[j]);
hash_ans += (mpa[s1[j]-'a'] * bas1 ^ mpb[s2[j]-'a'] * bas2);
bas1 *= base_a,bas2 = base_b;
}// printf("\n");
be[i] = hash_ans;b1[++lb1] = be[i];
s1 = s1.substr(0,fa),s2 = s2.substr(ga+1,s2.size()-1-ga);reverse(s1.begin(),s1.end());
// printf("s1 = %s s2 = %s\n",s1.c_str(),s2.c_str());
ps[i] = s1,ns[i] = s2;
}
for(int i = 1;i <= q;++i){string s1,s2;cin >> s1 >> s2;if(s1.size() != s2.size())continue;// 不可能产生贡献
int fa = 0,ga = s1.size()-1;ull hash_ans = 0,bas1 = 1,bas2 = 1;
while(s1[fa] == s2[fa])++fa;while(s1[ga] == s2[ga])--ga;
for(int j = fa;j <= ga;++j){
hash_ans += (mpa[s1[j]-'a'] * bas1 ^ mpb[s2[j]-'a'] * bas2);
bas1 *= base_a,bas2 = base_b;
}
ae[i] = hash_ans;b1[++lb1] = ae[i];
s1 = s1.substr(0,fa),s2 = s2.substr(ga+1,s2.size()-1-ga);reverse(s1.begin(),s1.end());
// printf("st1 = %s st2 = %s\n",s1.c_str(),s2.c_str());
pt[i] = s1,nt[i] = s2;
}
sort(b1+1,b1+lb1+1),lb1 = unique(b1+1,b1+lb1+1)-b1-1;
for(int i = 1;i <= n;++i){
if(!be[i])continue;
int pos = lower_bound(b1+1,b1+lb1+1,be[i])-b1;vop[pos].emplace_back(op{ps[i],ns[i]});
}
for(int i = 1;i <= q;++i){
if(!ae[i])continue;
int pos = lower_bound(b1+1,b1+lb1+1,ae[i])-b1;vqry[pos].emplace_back(qry{pt[i],nt[i],i});
}
for(int idx = 1;idx <= lb1;++idx){
// printf("idx = %d --------------------\n",idx);
// 先处理前缀
clear();
vector<op> &now_op = vop[idx];vector<qry> &now_qry = vqry[idx];
for(int i = 0;i < now_qry.size();++i)tmp_b[i] = insert(now_qry[i].n1);
for(int i = 0;i < now_op.size();++i)tmp_a[i] = insert(now_op[i].n1);
dfs(1);
for(int i = 0;i < now_op.size();++i)x1[i] = tree[tmp_a[i]].dfn,x2[i] = tree[tmp_a[i]].lv;
for(int i = 0;i < now_qry.size();++i)vb[i+1].x = tree[tmp_b[i]].dfn,vb[i+1].v = now_qry[i].idx;
// 再处理后缀
clear();
for(int i = 0;i < now_qry.size();++i)tmp_b[i] = insert(now_qry[i].n2);
for(int i = 0;i < now_op.size();++i)tmp_a[i] = insert(now_op[i].n2);
dfs(1);
for(int i = 0;i < now_op.size();++i)y1[i] = tree[tmp_a[i]].dfn,y2[i] = tree[tmp_a[i]].lv;
for(int i = 0;i < now_qry.size();++i)vb[i+1].y = tree[tmp_b[i]].dfn,b[i+1] = vb[i+1].y;
lvb = lb = now_qry.size();
// 离散化
sort(b+1,b+lb+1),lb = unique(b+1,b+lb+1)-b-1;lva = 0;
// printf("b = ");for(int i = 1;i <= lb;++i)printf("{%d}",b[i]);printf("\n");
for(int i = 0;i < now_op.size();++i){
// printf("(%d,%d) (%d,%d)\n",x1[i],y1[i],x2[i],y2[i]);
++x2[i];
y1[i] = lower_bound(b+1,b+lb+1,y1[i])-b,y2[i] = upper_bound(b+1,b+lb+1,y2[i])-b;
va[++lva] = point{x1[i],y1[i],1},va[++lva] = point{x2[i],y1[i],-1};
va[++lva] = point{x1[i],y2[i],-1},va[++lva] = point{x2[i],y2[i],1};
// printf("--(%d,%d) (%d,%d)\n",x1[i],y1[i],x2[i],y2[i]);
}
sort(va+1,va+lva+1,cmp),sort(vb+1,vb+lvb+1,cmp);int pos = 1;
for(int i = 1;i <= lvb;++i){
// printf("--(%d,%d %d]\n",vb[i].x,vb[i].y,vb[i].v);
while(pos <= lva && va[pos].x <= vb[i].x)add(va[pos].y,va[pos].v),++pos;
// printf("vb x = %d\n",vb[i].x);
vb[i].y = lower_bound(b+1,b+lb+1,vb[i].y)-b;
// printf("vb[%d].v = %d\n",i,vb[i].v);
ans[vb[i].v] = query(vb[i].y);
}
while(pos > 1)--pos,add(va[pos].y,-va[pos].v);
}
for(int i = 1;i <= q;++i)cout << ans[i] << '\n';
// cout << flush,system("pause");
return 0;
}后记：本人场上眼瞎没看到