题目大意
给定一个仅含小写英文字母的字符串 \(s\)，每次操作选择一个区间 \([l_i,r_i]\) 将 \(s\) 的该区间中的所有字母 \(x_i\) 全部替换成字母 \(y_i\)，问所有操作做完后，得到的字符串是什么。
输入的第一行包含一个字符串 \(s\)。
第二行包含一个整数 \(m\)。
接下来 \(m\) 行，每行包含 \(4\) 个参数 \(l_i,r_i,x_i,y_i\)，相邻两个参数之间用一个空格分隔，其中 \(l_i,r_i\) 为整数，\(x_i, y_i\) 为小写字母。
\(1 \leq |s|, m \leq 10^5\)，\(1 \leq l_i \leq r_i \leq |s|\)，\(x_i\neq y_i\)，其中 \(|s|\) 表示字符串 \(s\) 的长度。
思路
因为不会线段树分裂合并只能用普通做法。
按照题目开 \(26\) 棵权值线段树。
对于修改操作，我们遍历要修改的 \(x\) 线段树。
如果当前区间全为 \(x\) 那么直接在 \(y\) 那颗树上修改并打上覆盖标记。
if(ll>=l&&rr<=r&&sum(x,p)==rr-ll+1){
sum(y,p)=sum(x,p);
sum(x,p)=0;
chg(y,p)=1;chg(x,p)=0;
return ;
}
输出答案时，直接遍历 \(26\) 棵线段树即可。
注意线段树的空间。
Code
#include<bits/stdc++.h>
using namespace std;
#define LL int
#define Ld long double
#define sum(k,p) tree[k][p].sum
#define chg(k,p) tree[k][p].chg
const int N = 100005,M=100005;
LL m,l,r,n;
char ch[N],x,y;
struct Segment_tree{
LL sum,chg;
}tree[26][N*4];
void build(LL p,LL l,LL r){
for(int i=0;i<26;i++)chg(i,p)=-1;
if(l==r){
sum(ch[l]-'a',p)=1;
return ;
}
LL mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
for(int i=0;i<26;i++) sum(i,p)=sum(i,p<<1)+sum(i,p<<1|1);
return ;
}
void pushdown(LL p,LL k,LL l,LL r,LL mid){
if(chg(k,p)==-1) return ;
sum(k,p<<1)=(mid-l+1)*chg(k,p);
sum(k,p<<1|1)=(r-mid)*chg(k,p);
chg(k,p<<1)=chg(k,p<<1|1)=chg(k,p);
chg(k,p)=-1;
return ;
}
void pushup(LL p,LL k){
sum(k,p)=sum(k,p<<1)+sum(k,p<<1|1);
return ;
}
void change(LL p,LL l,LL r,LL x,LL y,LL ll,LL rr){
if(!sum(x,p)) return ;
if(ll>=l&&rr<=r&&sum(x,p)==rr-ll+1){
sum(y,p)=sum(x,p);
sum(x,p)=0;
chg(y,p)=1;chg(x,p)=0;
return ;
}
LL mid=(ll+rr)>>1;
pushdown(p,x,ll,rr,mid);
pushdown(p,y,ll,rr,mid);
if(l<=mid) change(p<<1,l,r,x,y,ll,mid);
if(r>mid) change(p<<1|1,l,r,x,y,mid+1,rr);
pushup(p,x);
pushup(p,y);
return ;
}
void out(LL p,LL l,LL r){
if(l==r){
for(int i=0;i<26;i++){
if(sum(i,p)!=0){
cout<<(char)(i+97);
break;
}
}
return ;
}
LL mid=(l+r)>>1;
for(int i=0;i<26;i++) pushdown(p,i,l,r,mid);
out(p<<1,l,mid);
out(p<<1|1,mid+1,r);
return ;
}
signed main(){
cin>>ch+1;
LL len=strlen(ch+1);
build(1,1,len);
cin>>n;
for(int i=1;i<=n;i++){
cin>>l>>r>>x>>y;
change(1,l,r,x-'a',y-'a',1,len);
}
out(1,1,len);
return 0;
}