我们把每个替换成的 $s$ 存一下，初始字符串 a 看作 $s_1$，其他往后移动。

开 $26$ 个队列，里面存一个二元组 $(i,j)$ 表示字符 $s_{i,j}$ 还是保持原状。每次更新的时候把它们拿出来，修改 $to_{i,j}$ 为当前 $s$ 的下标，表示这个字符已经被替换成了 $s_{to_{i,j}}$。

如果某个 $s_{i,j}$ 还是原状（就是它的字面量），则 $to_{i,j} = 0$。

题目要求求出最后的 $S_{l \dots r}$，$l,r$ 可能很大，那么我们只需要求出每个 $s_i$ 被解码之后的大小 $siz_i$，按位确定区间，然后深搜一层一层解码即可。

注意到这个东西很像一个 DAG，某个字符指向后面的字符串，也就是 $to_{i,j} > i$。于是建反图拓扑排序 DP 下贡献就好了。你甚至不用显式写出拓扑排序，从大到小枚举即可。注意可能要爆 long long，加的时候要处理和一个很大值取 $\min$。

#include<bits/stdc++.h>
using namespace std;
const long long limit=3e18;
long long l,r,siz[200020];
int n;
vector<int> to[200020];
queue<pair<int,int> > q[30];
string s[200020];
void add(long long &a,long long &b){
	a=min(limit,a+b);
}
void dfs(int x,long long now){
	for(int i=0;i<s[x].size();i++){
		if(now>=r)return;
		long long n2=now;
		add(now,siz[to[x][i]]);
		if(now>=l){
			if(!to[x][i])cout<<s[x][i];
			else dfs(to[x][i],n2); 
		}
	}
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
	cin>>l>>r>>n;
	
	siz[0]=1;
	
	s[1]="a";
	to[1].push_back(0);
	q[0].push({1,0});
	n++;
	
	for(int i=2;i<=n;i++){
		char c;
		cin>>c>>s[i];
		to[i].resize(s[i].size());
		c-='a';
		while(!q[c].empty()){
			auto _=q[c].front();
			q[c].pop();
			to[_.first][_.second]=i;
		}
		for(int j=0;j<s[i].size();j++){
			q[s[i][j]-'a'].push({i,j});
		}
	}
	
	for(int i=n;i>=1;i--){
		for(int j:to[i]){
			add(siz[i],siz[j]);
		}
	}
//	for(int i=1;i<=n;i++)cerr<<siz[i]<<'\n';
	dfs(1,0);






	return 0;
}

提交，诶我测怎么 TLE 54pts 了。哦哦有可能会被卡到 $O(n^2)$ 是吧。

我们充分发扬人类智慧，如果递归的时候要的是某个字符串解码后的全部展开，那么我们就把它记忆化下来，以后再遇到同样的查询时就可以直接用了。

实现方式是把 cout 换成 ans+=...，然后在循环前后记录一下 ans 长度，用一个二元组存储本次递归给 ans 加的是子串 $[l,r]$。当然代码里面为了适应 substr 的用法是 $l$ 和 $r-l+1$。

如果再次遇到要这个字符串解码后的全部展开，就直接 ans+=ans.substr(mem[x].first,mem[x].second); 后返回。

这样速度快得飞起，在 $2 \times 10^5$ 的数据下都可以在 38ms 内卡过。

复杂度乱证明：不是“要某个字符串解码后的全部展开”的递归最多只有两次，这两次没法记忆化，是 $O(n)$，其他的记忆化一遍就拿来用，也是 $O(n)$。

听上去很假但确实过了，欢迎 hack/证明/证伪。

#include<bits/stdc++.h>
using namespace std;
const long long limit=3e18;
long long l,r,siz[200020];
int n;
vector<int> to[200020];
queue<pair<int,int> > q[30];
string s[200020],ans;
pair<int,int> mem[200020];
void add(long long &a,long long &b){
	a=min(limit,a+b);
}
void dfs(int x,long long now){
//	cerr<<x<<' '<<now<<'\n';
	bool _=l<=now&&now+siz[x]<=r;
	if(_&&mem[x].first!=-1){
		ans+=ans.substr(mem[x].first,mem[x].second);
		return ;
	}
	int st=ans.size();
	for(int i=0;i<s[x].size();i++){
		if(now>=r)return;
		long long n2=now;
		add(now,siz[to[x][i]]);
		if(now>=l){
			if(!to[x][i]){
				ans+=s[x][i];
			}
			else dfs(to[x][i],n2); 
		}
	}
	int ed=ans.size();
	if(_)mem[x]={st,ed-st};
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
	cin>>l>>r>>n;
	
	siz[0]=1;
	
	s[1]="a";
	to[1].push_back(0);
	q[0].push({1,0});
	n++;
	
	for(int i=2;i<=n;i++){
		char c;
		cin>>c>>s[i];
		to[i].resize(s[i].size());
		c-='a';
		while(!q[c].empty()){
			auto _=q[c].front();
			q[c].pop();
			to[_.first][_.second]=i;
		}
		for(int j=0;j<s[i].size();j++){
			q[s[i][j]-'a'].push({i,j});
		}
	}
	
	for(int i=n;i>=1;i--){
		for(int j:to[i]){
			add(siz[i],siz[j]);
		}
	}
	for(int i=1;i<=n;i++)mem[i]={-1,-1};
	dfs(1,0);
	cout<<ans;




	return 0;
}