专栏文章

replace Trie 套 Trie 另解

ll1ng21y12026
P14363题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mind0ski
此快照首次捕获于
2025/12/02 00:24
3 个月前
此快照最后确认于
2025/12/02 00:24
3 个月前
查看原文
Trie 套 Trie 做法。
前情提要：赛时调 T3 调小样例调到最后一分钟。没有测试大样例。赛后一度认为自己会挂，出分过了\ouo/
省略若干转化，问题即现在有若干 (ai,bi)(a_i,b_i) 每次询问 (pi,qi)(p_i,q_i)，满足 aia_i 是 pip_i 前缀，bib_i 是 qiq_i 前缀的 (ai,bi)(a_i,b_i) 数目。
考虑对 aia_i 建 Trie，并在代表 aia_i 的节点上开一棵子 Trie，存储 bib_i，并在 bib_i 处标记 +1+1。
对于一个询问，令 pip_i 到 Trie 的根上所有子 Trie 合并后为 TrieA，即询问问 A 上 qiq_i 到 A 的根上的标记总和。
将询问挂在 pip_i 点，并考虑如下合并过程：每进入一个节点，将这个节点上的 Trie 与 A 合并。每退出一个节点，将 A 中它的贡献减去。
不难发现到达一个点 xx 时，A 恰好为 xx 到根上所有子 Trie 合并后的 Trie。直接处理该点的询问即可。
使用类似线段树合并的技巧。我们可以做到每个节点的 Trie 只被合并、删除一次，时间复杂度为 O(ΣL)O(\Sigma L)，空间复杂度为 O(ΣL)O(\Sigma L)。其中 Σ\Sigma 为字符集大小 2626。
放一下场上源码纪念一下：
C
#include<bits/stdc++.h>
#define rg register int
#define fo(i,l,r) for(rg i=(l);i<=(r);i++)
#define dfo(i,r,l) for(rg i=(r);i>=(l);i--)
#define fe(i,x) for(rg i=hd[x];i;i=nex[i])
#define frein freopen("in.txt","r",stdin)
#define freout freopen("out.txt","w",stdout)
#define fre(p) freopen(#p".in","r",stdin),freopen(#p".out","w",stdout)
#define vi vector<int>
#define eb emplace_back
#define pii pair<int,int>
#define fir first
#define sec second
#define mkp make_pair
#define i8 __int128
#define db double
#define ll unsigned long long
using namespace std;
bool deb=1,Mst;
void ck_(){cerr<<"\n";}
template<typename T,typename...R>
void ck_(T x,R...y){if(!deb)return;cerr<<x<<" ";ck_(y...);}
void Bz_(){cerr<<"---------------------------------\n";}
#define ck ck_
#define Bz Bz_()
#define outa(l,r,a) {fo(II,l,r)cerr<<a[II]<<" ";cerr<<"\n";}
#define gc() getchar()
#define pc(x) putchar(x)
inline void rd(string &a)
{
	register char c=gc();a="";
	while(c<'a'||'z'<c)c=gc();
	while('a'<=c&&c<='z')a+=c,c=gc();
}
void wt(int x)
{
	if(x<=9)pc(x+'0');
	else wt(x/10),pc(x%10+'0');
}
const int N=2e5+5,M=7e6+5;
ll bas=233,s;
string s1,s2;int l1,l2;
int n,m,x,y,t;
struct nd{string a,b;ll c;int i;}a[N],q[N];int lq,Ans[N];
vi h[M];
int lb,lc,b[M][26],rt[M],c[M][26],d[M],rf;
inline void init()
{
	fo(i,0,lb)fo(j,0,25)b[i][j]=0;
	fo(i,0,lc)fo(j,0,25)c[i][j]=0;
	fo(i,0,lb)rt[i]=0,h[i].clear();
	fo(i,0,lc)d[i]=0;
	lb=1,lc=0,rf=0;
}
inline void ins(nd o)
{
	int x=1,l=o.a.size();
	fo(i,0,l-1)
	{
		int &y=b[x][o.a[i]-'a'];
		if(y==0)y=++lb;
		x=y;
	}
	if(rt[x]==0)rt[x]=++lc;
	x=rt[x],l=o.b.size();
	fo(i,0,l-1)
	{
		int &y=c[x][o.b[i]-'a'];
		if(y==0)y=++lc;
		x=y;
	}
	d[x]++;
//	ck(o.a,o.b,o.c,x,d[x]);
}
inline void tag(nd o,int id)
{
	int x=1,l=o.a.size();
	fo(i,0,l-1)
	{
		if(b[x][o.a[i]-'a']==0)
		{
			h[x].eb(id);
			return;
		}
		x=b[x][o.a[i]-'a'];
	}
	h[x].eb(id);
}
void mg(int &x,int y)
{
	if(x==0)
	{
		x=y,d[x]=d[y];
		return;
	}
	d[x]+=d[y];
	fo(i,0,25)if(c[y][i])mg(c[x][i],c[y][i]);
}
void del(int x,int y)
{
	d[x]-=d[y];
	fo(i,0,25)if(c[y][i])del(c[x][i],c[y][i]);
}
void wk(int x)
{
	if(x==0)return;
	mg(rf,rt[x]);
	for(int o:h[x])
	{
		int z=rf,l=q[o].b.size();
		Ans[q[o].i]+=d[z];
		fo(i,0,l-1)
		{
			z=c[z][q[o].b[i]-'a'];
			Ans[q[o].i]+=d[z];
		}
	}
	fo(i,0,25)wk(b[x][i]);
	del(rf,rt[x]);
}
bool Med;
int main()
{
//	frein;
//	freout;
	fre(replace);
	cin>>n>>m;
//	ck((&Mst-&Med)/1024);
	fo(j,1,n)
	{
		rd(s1),rd(s2),l1=s1.size()-1;
		fo(i,0,l1)
		{
			x=i;
			if(s1[i]!=s2[i])break;
		}
		dfo(i,x-1,0)a[j].a+=s1[i];
		dfo(i,l1,0)
		{
			y=i;
			if(s1[i]!=s2[i])break;
		}
		fo(i,y+1,l1)a[j].b+=s1[i];
		a[j].c=0;
		fo(i,x,y)a[j].c=a[j].c*bas+s1[i];
		fo(i,x,y)a[j].c=a[j].c*bas+s2[i];
		a[j].i=j;
//		ck(a[j].a,a[j].b,a[j].c);
//		if(j==206)cout<<s1<<" "<<s2<<"\n";
	}
	fo(j,1,m)
	{
		rd(s1),rd(s2),l1=s1.size()-1,l2=s2.size()-1;
		if(l1!=l2)
		{
			Ans[j]=0;
			continue;
		}lq++;
		fo(i,0,l1)
		{
			x=i;
			if(s1[i]!=s2[i])break;
		}
		dfo(i,x-1,0)q[lq].a+=s1[i];
		dfo(i,l1,0)
		{
			y=i;
			if(s1[i]!=s2[i])break;
		}
		fo(i,y+1,l1)q[lq].b+=s1[i];
		q[lq].c=0;
		fo(i,x,y)q[lq].c=q[lq].c*bas+s1[i];
		fo(i,x,y)q[lq].c=q[lq].c*bas+s2[i];
		q[lq].i=j;
//		ck(q[lq].a,q[lq].b,q[lq].c);
//		if(j==177)cout<<s1<<" "<<s2<<"\n";
//		ck(s1);ck(s2);
	}
//	Bz;
	sort(a+1,a+1+n,[](nd a,nd b){return a.c<b.c;});
	sort(q+1,q+1+lq,[](nd a,nd b){return a.c<b.c;});
//	fo(k,1,lq)
//	{
//		int qa=q[k].a.size(),qb=q[k].b.size();
//		fo(i,1,n)if(a[i].c==q[k].c)//if(i==30399)
//		{
//			bool p=0;
//			int l=a[i].a.size();
//			if(l>qa)continue;
//			fo(j,0,l-1)if(a[i].a[j]!=q[k].a[j]){p=1;break;}
//			if(p)continue;
//			l=a[i].b.size();
//			if(l>qb)continue;
//			fo(j,0,l-1)if(a[i].b[j]!=q[k].b[j]){p=1;break;}
//			if(p==0)
//			{
//				Ans[q[k].i]++;
//				cout<<a[i].i<<" "<<a[i].a<<" "<<a[i].b<<"\n";
//			}
//		}
//	}
	int pos=1;init();
	fo(i,1,n)
	{
		ins(a[i]);
		if(i==n||a[i].c!=a[i+1].c)
		{
			while(pos<=lq&&q[pos].c<a[i].c)pos++;
			while(pos<=lq&&q[pos].c==a[i].c)
			{
				tag(q[pos],pos);
				pos++;
			}
			wk(1);
			init();
		}
	}
	fo(i,1,m)wt(Ans[i]),pc('\n');
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...