给定一个仅含小写英文字母的字符串 \(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;
}

AC Record