题面
给定一个仅含小写英文字母的字符串 \(s\) 和 \(m\) 次操作，每次操作选择一个区间 \([l_i,r_i]\) 将 \(s\) 的该区间中的所有字母 \(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\) 的长度。
思路
首先我写了一个蹩脚的 FHQ-Treap，后来被我证伪了……
其实这道题是一个线段树合并 / 分裂 水题。
首先先按照 \(s\) 的值域建出 \(26\) 棵线段树。对于每一个 \(s_i\)，用第 \(s_i\) 个线段树将第 \(i\) 个元素修改为 \(1\)（也就是，存在）。
然后修改的时候直接将 \([l_i,r_i]\) 从第 \(x_i\) 个线段树上分裂下来，合并到第 \(y_i\) 个线段树上，也就可以了。
最后输出的时候暴力枚举值域，找到存在的输出即可。
时间复杂度 \(O(m\log|s_i|)\)。
另外本题有双倍经验 Codeforces911G Mass Change Queries，代码就不放了，具体看 Codeforces 提交记录。
代码
#include <bits/stdc++.h>
#define int long long
#define ls(i) (t[i].ls)
#define rs(i) (t[i].rs)
#define mid ((l+r)>>1)
using namespace std;
const int N = 1e5+5;
struct node{
int ls,rs,v;
} t[N<<8];
int root[30],tot;
inline void newnode(int &i){
if(!i)i=(++tot);
}
void update(int p,int v,int &i,int l,int r){
newnode(i);
if(l==r){
t[i].v=v;
return;
}
if(p<=mid){
update(p,v,ls(i),l,mid);
}
else{
update(p,v,rs(i),mid+1,r);
}
}
int split(int ql,int qr,int &i,int l,int r){
int p=0;
newnode(p);
if(ql<=l&&r<=qr){
t[p]=t[i];
i=0;
}
else{
if(ql<=mid){
ls(p)=split(ql,qr,ls(i),l,mid);
}
if(qr>mid){
rs(p)=split(ql,qr,rs(i),mid+1,r);
}
}
return p;
}
void merge(int &x,int &y){
if(x==0||y==0){
if(y)x=y;
if(x)y=x;
return;
}
t[x].v+=t[y].v;
merge(ls(x),ls(y));
merge(rs(x),rs(y));
}
int query(int p,int i,int l,int r){
if(!i)return 0;
if(l==r){
return t[i].v;
}
if(p<=mid){
return query(p,ls(i),l,mid);
}
else{
return query(p,rs(i),mid+1,r);
}
}
char s[N];
int n,m;
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>(s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++){
update(i,1,root[s[i]-'a'],1,n);
}
cin>>m;
while(m--){
int li,ri,x,y;char xi,yi;
cin>>li>>ri>>xi>>yi;
x=xi-'a',y=yi-'a';
int ytxy_ak_ioi = split(li,ri,root[x],1,n);
merge(root[y],ytxy_ak_ioi);
}
for(int i=1;i<=n;i++){
for(char j='a';j<='z';j++){
if(query(i,root[j-'a'],1,n)>0){
cout<<j;
break;
}
}
}
return 0;
return 0;
}