- 题解
- @ 2026-11-17 19:29:41
三字典树+离线差分树状数组
这波不抢最优解(喵呜?本喵log时间复杂度跟人家线性的怎么比?)
那就说说为什么要切这道看似毫无吊用的蓝色字符串吧(其实就是毫无吊用)
因为这是我参加S组以来T3T4考场骗分最高的一题,考场代码足足拿了50分,紫题(后来降的蓝)能骗到50分,代码甚至sub1500B,祖坟都要冒青烟了喵,这波直接助力我拿到S组国一。再加上我对字典树的情有独钟,就在备赛NOIP的时候顺手切了嘿嘿
足足花了我10个小时喵呜……
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,an[200005],cn=0;
struct T
{
vector<int>h,t,x;
vector<unsigned char>c;
T()
{
h.push_back(-1);
}
void rv(int s)
{
h.reserve(s);
if(s>1)
{
t.reserve(s-1);
x.reserve(s-1);
c.reserve(s-1);
}
}
int ad(const string&s)
{
int u=0;
for(char ch:s)
{
int cc=ch-'a',e=h[u],v=-1;
while(e!=-1)
{
if(c[e]==cc)
{
v=t[e];break;
}
e=x[e];
}
if(v==-1)
{
v=h.size();
h.push_back(-1);
int d=t.size();
t.push_back(v);
c.push_back(cc);
x.push_back(h[u]);
h[u]=d;
}
u=v;
}
return u;
}
int go(const string&s)
{
int u=0;
for(char ch:s)
{
int cc=ch-'a',e=h[u],v=-1;
while(e!=-1)
{
if(c[e]==cc)
{
v=t[e];break;
}
e=x[e];
}
if(v==-1) break;
u=v;
}
return u;
}
};
struct F
{
int n;
vector<int>t;
F(int m=0)
{
n=m;
t.assign(m+2,0);
}
void ad(int p,int v)
{
for(int i=p+1;i<(int)t.size();i+=i&-i)
t[i]+=v;
}
void rg(int l,int r,int v)
{
ad(l,v);
ad(r,-v);
}
int sm(int p)
{
int s=0;
for(int i=p+1;i>0;i-=i&-i)
s+=t[i];
return s;
}
};
void eu(const T&r,vector<int>&a,vector<int>&b)
{
int m=r.h.size();
a.assign(m,0);
b.assign(m,0);
vector<int>it=r.h,st;
st.reserve(m);
st.push_back(0);
int tm=0;
a[0]=tm++;
while(!st.empty())
{
int u=st.back(),&e=it[u];
if(e!=-1)
{
int v=r.t[e];
e=r.x[e];
a[v]=tm++;
st.push_back(v);
}
else
{
b[u]=tm;
st.pop_back();
}
}
}
struct R
{
string p,e;
};
struct Q
{
string p,e;
int id;
};
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>q;
unordered_map<string,int>mp;
mp.reserve((n+q)*2+10);
mp.max_load_factor(0.7);
vector<vector<int>>gr(n+1),gq(n+1);
vector<R>rs;
vector<Q>qs;
rs.reserve(n);
qs.reserve(q);
for(int i=1;i<=n;i++)
{
string a,b;
cin>>a>>b;
int L=a.size(),u=0;
while(u<L&&a[u]==b[u])u++;
if(u==L) continue;
int v=L-1;
while(v>=u&&a[v]==b[v])v--;
string p;
for(int j=u-1;j>=0;j--)p+=a[j];
string e;
for(int j=v+1;j<L;j++)e+=a[j];
int m=v-u+1;
string k=a.substr(u,m)+b.substr(u,m);
auto it=mp.find(k);
int g;
if(it==mp.end())
{
g=++cn;
mp.emplace(k,g);
}
else g=it->second;
rs.push_back({p,e});
gr[g].push_back(rs.size()-1);
}
for(int id=0;id<q;id++)
{
string a,b;
cin>>a>>b;
an[id]=0;
if(a.size()!=b.size()) continue;
int L=a.size(),u=0;
while(u<L&&a[u]==b[u])u++;
if(u==L) continue;
int v=L-1;
while(v>=u&&a[v]==b[v])v--;
string p;
for(int j=u-1;j>=0;j--)p+=a[j];
string e;
for(int j=v+1;j<L;j++)e+=a[j];
int m=v-u+1;
string k=a.substr(u,m)+b.substr(u,m);
auto it=mp.find(k);
if(it==mp.end()) continue;
int g=it->second;
qs.push_back({p,e,id});
gq[g].push_back(qs.size()-1);
}
for(int g=1;g<=cn;g++)
{
if(gq[g].empty()) continue;
auto&ri=gr[g];
auto&qi=gq[g];
int nr=ri.size(),nq=qi.size();
int sp=0,se=0;
for(int i:ri)
{
sp+=rs[i].p.size();
se+=rs[i].e.size();
}
T tp,te;
tp.rv(sp+1);
te.rv(se+1);
vector<int>pn(nr),en(nr);
for(int i=0;i<nr;i++)
{
pn[i]=tp.ad(rs[ri[i]].p);
en[i]=te.ad(rs[ri[i]].e);
}
int M=te.h.size();
vector<int>ti,to;
eu(te,ti,to);
int P=tp.h.size();
vector<int>rh(P,-1),rn(nr);
for(int i=0;i<nr;i++)
{
int u=pn[i];
rn[i]=rh[u];
rh[u]=i;
}
vector<int>qh(P,-1),qn(nq),qe(nq),qq(nq);
for(int j=0;j<nq;j++)
{
Q&x=qs[qi[j]];
int u=tp.go(x.p),v=te.go(x.e);
qe[j]=v;
qq[j]=x.id;
qn[j]=qh[u];
qh[u]=j;
}
F f(M);
vector<pair<int,int>>st;
st.push_back({0,0});
while(!st.empty())
{
int u=st.back().first,s=st.back().second;
st.pop_back();
if(s==0)
{
for(int e=rh[u];e!=-1;e=rn[e])
{
int v=en[e];
f.rg(ti[v],to[v],1);
}
for(int j=qh[u];j!=-1;j=qn[j])
{
int v=qe[j];
an[qq[j]]=f.sm(ti[v]);
}
st.push_back({u,1});
for(int e=tp.h[u];e!=-1;e=tp.x[e])
st.push_back({tp.t[e],0});
}
else
{
for(int e=rh[u];e!=-1;e=rn[e])
{
int v=en[e];
f.rg(ti[v],to[v],-1);
}
}
}
}
for(int i=0;i<q;i++)cout<<an[i]<<'\n';
return 0;
}
0 条评论
目前还没有评论...