记录编号	578531	评测结果	AAAAAAAAAAAAAAA
题目名称	[USACO23 Jan Gold] Find and Replace	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	0.151 s
提交时间	2023-03-27 19:47:46	内存使用	8.94 MiB

#include<bits/stdc++.h>
using namespace std;
const long long INF=1e18;
const int N=200105;
struct Node{
    char v;
    int lc,rc;
    long long sz;
} tr[N];
int root[26],ck;
char c[N];
string s[N];
void query(int u,long long l,long long r){
    if(r<=0||l>tr[u].sz){
    	return;	
	}
    if(tr[u].v=='#'){
        query(tr[u].lc,l,r);
        query(tr[u].rc,l-tr[tr[u].lc].sz,r-tr[tr[u].lc].sz);
    }
	else{
        putchar(tr[u].v);
    }
}
int main(){
	freopen("farg.in","r",stdin);
	freopen("farg.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    long long l,r,n;
    cin>>l>>r>>n;
    for(int i=1;i<=n;i++){
    	cin>>c[i]>>s[i];
	}
    for(int i=0;i<26;i++){
        tr[++ck]={char('a'+i),0,0,1};
        root[i]=ck;
    }
    for(int i=n;i>=1;i--){
        int now=0;
        for(auto x:s[i]){
            x-='a';
            if(now==0){
            	now=root[x];
			}
            else{
                tr[++ck]={'#',now,root[x],min(INF,tr[now].sz+tr[root[x]].sz)};
                now=ck;
            }
        }
        root[c[i]-'a']=now;
    }
    query(root[0],l,r);
    return 0;
}