题意：给定一个字符串，以及m次操作，每次操作对字符串的一个子区间进行升序或降序排序，求m次操作后的串
考虑桶排，发现线段树可以模拟桶排的过程，所以对26个字母分别建立线段树即可
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000000+10
struct tree{int sum,tag;}tr[MAXN*][];
char s[MAXN];
int n,m,cnt[];
void pushup(int k,int x){tr[k][x].sum=tr[k<<][x].sum+tr[k<<|][x].sum;}
void pushdown(int k,int x,int l,int r){
int mid=(l+r)>>;
if(tr[k][x].tag==){
tr[k<<][x].sum=(mid-l+);tr[k<<|][x].sum=(r-mid);
tr[k<<][x].tag=tr[k<<|][x].tag=;
tr[k][x].tag=;
}
else if(tr[k][x].tag==){
tr[k<<][x].sum=tr[k<<|][x].sum=;
tr[k<<][x].tag=tr[k<<|][x].tag=;
tr[k][x].tag=;
}
}
void build(int k,int l,int r,int x){
tr[k][x].tag=;
if(l==r){
tr[k][x].sum=;
return;
}
int mid=(l+r)>>;
build(k<<,l,mid,x);
build(k<<|,mid+,r,x);
pushup(k,x);
}
void update(int k,int l,int r,int L,int R,int val,int x){
if(l>=L&&r<=R){
if(val==)tr[k][x].sum=r-l+;
else tr[k][x].sum=;
tr[k][x].tag=val;
return;
}
pushdown(k,x,l,r);
int mid=(l+r)>>;
if(R<=mid)update(k<<,l,mid,L,R,val,x);
else if(L>mid)update(k<<|,mid+,r,L,R,val,x);
else update(k<<,l,mid,L,R,val,x),update(k<<|,mid+,r,L,R,val,x);
pushup(k,x);
}
int query(int k,int l,int r,int L,int R,int x){
if(l>=L&&r<=R)return tr[k][x].sum;
pushdown(k,x,l,r);
int mid=(l+r)>>;
if(R<=mid)return query(k<<,l,mid,L,R,x);
else if(L>mid)return query(k<<|,mid+,r,L,R,x);
else return query(k<<,l,mid,L,R,x)+query(k<<|,mid+,r,L,R,x);
pushup(k,x);
}
int main(){
scanf("%d%d",&n,&m);
scanf("%s",s+);
for(int i=;i<;i++)build(,,n,i);
for(int i=;i<=n;i++)update(,,n,i,i,,s[i]-'a');
while(m--){
memset(cnt,,sizeof(cnt));
int l,r,x;
scanf("%d%d%d",&l,&r,&x);
for(int i=;i<;i++){
cnt[i]=query(,,n,l,r,i);
update(,,n,l,r,,i);
}
if(x){
int p=l;
for(int i=;i<;i++){
if(cnt[i])update(,,n,p,p+cnt[i]-,,i);
p+=cnt[i];
}
}
else{
int p=l;
for(int i=;i>=;i--){
if(cnt[i])update(,,n,p,p+cnt[i]-,,i);
p+=cnt[i];
}
}
}
for(int i=;i<=n;i++){
for(int k=;k<;k++)
if(query(,,n,i,i,k)){
putchar((char)k+'a');
break;
}
}
return ;
}