看到这个做法很直接啊。

用一颗线段树维护每个颜色区间出现的次数。

在线段树上二分，找出前 $q$ 个该颜色出现的区间。

用 tag 维护所有颜色的转换，更新时把颜色数加到对应的新颜色上，并与原来的标记结合。

复杂度 $O(n\log n)$，但是有不小于 $5$ 倍的常数。

笔者使用了动态开点以减少一些空间的压力。

#include <bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
const int N=2e6+5;
char C,P;
int n,m,rt,tot,S[5],T[5];
int ls[N],rs[N],s[N][5],t[N][5];
void mt(int p,int f){
    memset(S,0,sizeof(S));
    memset(T,0,sizeof(T));
    for(int i=0;i<5;++i){
        S[t[f][i]]+=s[p][i];
        T[i]=t[f][t[p][i]];
    }for(int i=0;i<5;++i)
        s[p][i]=S[i],t[p][i]=T[i];
}void pd(int p){
    mt(ls[p],p),mt(rs[p],p);
    for(int i=0;i<5;++i)
        t[p][i]=i;
}void bd(int &p,int l,int r){
    p=++tot;
    for(int i=0;i<5;++i)
        t[p][i]=i;
    if(l==r){cin>>C,s[p][C-'a']=1;return;}
    bd(ls[p],l,mid),bd(rs[p],mid+1,r);
    for(int i=0;i<5;++i)
        s[p][i]=s[ls[p]][i]+s[rs[p]][i];
}void upd(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R)return mt(p,0);pd(p);
    if(L<=mid)upd(ls[p],l,mid,L,R);
    if(mid<R)upd(rs[p],mid+1,r,L,R);
    for(int i=0;i<5;++i)
        s[p][i]=s[ls[p]][i]+s[rs[p]][i];
}int ask(int p,int l,int r,int x,int k){
    if(l==r)return l;pd(p);
    if(s[ls[p]][x]>=k)
        return ask(ls[p],l,mid,x,k);
    return ask(rs[p],mid+1,r,x,k-s[ls[p]][x]);
}void prt(int p,int l,int r){
    if(l==r){
        for(int i=0;i<5;++i)
            if(s[p][i])cout<<char(i+'a');
    }else pd(p),prt(ls[p],l,mid),prt(rs[p],mid+1,r);
}signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    cin>>n>>m,bd(rt,1,n);
    for(int x,y;m;--m){
        cin>>x>>C>>P;
        y=ask(rt,1,n,C-'a',x);
        for(int i=0;i<5;++i)
            t[0][i]=i;
        t[0][C-'a']=P-'a';
        upd(rt,1,n,1,y);
    }prt(rt,1,n);
    return 0;
}