题解：P12921 [POI 2021/2022 R3] 挑剔的 Bajtazar / Wybredny Bajtazar

#include<iostream>
#include<algorithm>
const int sz=1e6+10;
std::string s;
struct SegT{
  int sum[sz<<2][5],tag[sz<<2][5];
  void build(int p,int ln,int rn){
    for(int x:{0,1,2,3,4})tag[p][x]=x;
    if(ln==rn)return sum[p][s[ln]-'a']=1,void();
    int mid=ln+rn>>1;
    build(p<<1,ln,mid);
    build(p<<1|1,mid+1,rn);
    for(int x:{0,1,2,3,4})sum[p][x]=sum[p<<1][x]+sum[p<<1|1][x];
  }
  void push(int p,int trs[5]){
    static std::basic_string<int>S(5,0),T(5,0);
    S.assign(5,0),T.assign(5,0);
    for(int x:{0,1,2,3,4})S[trs[x]]+=sum[p][x],T[x]=trs[tag[p][x]];
    for(int x:{0,1,2,3,4})sum[p][x]=S[x],tag[p][x]=T[x];
  }
  void pushdown(int p,int ln,int rn){
    push(p<<1,tag[p]),push(p<<1|1,tag[p]);
    for(int x:{0,1,2,3,4})tag[p][x]=x;
  }
  void change(int p,int ln,int rn,int l,int r,int trs[5]){
    if(ln>=l&&rn<=r)return push(p,trs);
    int mid=ln+rn>>1;
    pushdown(p,ln,rn);
    if(l<=mid)change(p<<1,ln,mid,l,r,trs);
    if(r>mid)change(p<<1|1,mid+1,rn,l,r,trs);
    for(int x:{0,1,2,3,4})sum[p][x]=sum[p<<1][x]+sum[p<<1|1][x];
  }
  int find(int p,int ln,int rn,int x,int k){
    if(ln==rn)return ln;
    int mid=ln+rn>>1;
    pushdown(p,ln,rn);
    if(sum[p<<1][x]>=k)return find(p<<1,ln,mid,x,k);
    else return find(p<<1|1,mid+1,rn,x,k-sum[p<<1][x]);
  }
  void print(int p,int ln,int rn){
    if(ln==rn){
      for(int x:{0,1,2,3,4})
        if(sum[p][x]!=0)std::cout<<(char)(x+'a');
      return;
    }
    int mid=ln+rn>>1;
    pushdown(p,ln,rn);
    print(p<<1,ln,mid);
    print(p<<1|1,mid+1,rn);
  }
}st;
int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n,q;
  std::cin>>n>>q>>s,s=" "+s;
  st.build(1,1,n);
  while(q--){
    int p;
    char a,b;
    std::cin>>p>>a>>b;
    int T[]={0,1,2,3,4};
    T[a-'a']=b-'a';
    int pos=st.find(1,1,n,a-'a',p);
    st.change(1,1,n,1,pos,T);
  }
  st.print(1,1,n);
  std::cout<<"\n";
  return 0;
}