开一颗珂朵莉树，对于每个新的查询，先把l-1,l之间和r,r+1之间split开，然后对于剩下的部份用桶排序并暴力合并即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
using namespace std;
const int N=100005;
struct Data{
int l;int r;char id;
bool operator<(const Data &B)const{
return r<B.r;
}
};
int n,q;
char ch[N];
std::set<Data> st;
inline void split(std::set<Data>::iterator it, int X){
int l=it->l,r=it->r;char id=it->id;
if(X<l||X>=r){
return;
}
st.erase(it);st.insert((Data){l,X,id});st.insert((Data){X+1,r,id});
}
int bckt[30];
inline void clr(){
for(int i=0;i<26;++i){
bckt[i]=0;
}
}
inline void uni(int l,int r,int op){
std::set<Data>::iterator itx,ity;
itx=st.lower_bound((Data){0,l-1,0});
split(itx,l-1);
ity=st.lower_bound((Data){0,r,0});
split(ity,r);
itx=st.lower_bound((Data){0,l,0});
ity=st.lower_bound((Data){0,r,0});
++ity;
for(std::set<Data>::iterator it=itx;it!=ity;++it){
bckt[(it->id)-'a']+=(it->r)-(it->l)+1;
}
st.erase(itx,ity);
int loc,nl=l;
for(int i=0;i<26;++i){
loc=op?i:(26-i-1);
if(bckt[loc]<=0){
continue;
}
st.insert((Data){nl,nl+bckt[loc]-1,'a'+loc});
nl+=bckt[loc];
}
clr();
}
inline void prnt(){
for(std::set<Data>::iterator it=st.begin();it!=st.end();++it){
for(int j=it->l;j<=it->r;++j){
putchar(it->id);
}
}
puts("");
}
inline void init(){
scanf("%d%d",&n,&q);
std::cin>>ch+1;
for(int i=1;i<=n;++i){
st.insert((Data){i,i,ch[i]});
}
int l,r,op;
for(int i=1;i<=q;++i){
scanf("%d%d%d",&l,&r,&op);
uni(l,r,op);
// prnt();
}
prnt();
}
int main(){
init();
return 0;
}