题解
这道题给你两个操作，一个升序，一个降序
我们可以观察到这个字符串都是由小写字母组成的，只有26个字符，所以我们开一个26个字符的线段树
每次查询的时候找到这个区间内‘a'到'z'的数量，再判断一下要升序还是降序就可以喽
#include<bits/stdc++.h>
#define L 100005
using namespace std;
int n,m,l,r,x;
int mark[*L][],tree[*L][];
char s[L];
void build(int v,int l,int r){
if (l==r){
tree[v][s[l]-'a']=;
return;
}
int mid=(l+r)>>;
build(v<<,l,mid);
build(v<<|,mid+,r);
for (int i=;i<;i++)
tree[v][i]=tree[v<<][i]+tree[v<<|][i];
}
void pushdown(int v,int k,int l,int r){
int mid=(l+r)>>;
if (mark[v][k]){
mark[v<<][k]=mark[v][k];
mark[v<<|][k]=mark[v][k];
if (mark[v][k]&)
tree[v<<][k]=tree[v<<|][k]=;
else{
tree[v<<][k]=mid-l+;
tree[v<<|][k]=r-mid;
}
mark[v][k]=;
}
}
void change(int v,int l,int r,int x,int y,int k,int key){
if (mark[v][k]==key+) return;
if (x<=l&&y>=r){
mark[v][k]=key+;
if (!key) tree[v][k]=;
else tree[v][k]=r-l+;
return;
}
pushdown(v,k,l,r);
int mid=(l+r)>>;
if (y<=mid) change(v<<,l,mid,x,y,k,key); else
if (x>mid) change(v<<|,mid+,r,x,y,k,key);
else{
change(v<<,l,mid,x,mid,k,key);
change(v<<|,mid+,r,mid+,y,k,key);
}
tree[v][k]=tree[v<<][k]+tree[v<<|][k];
}
int query(int v,int l,int r,int x,int y,int k){
if (!tree[v][k]) return ;
if (x<=l&&y>=r) return tree[v][k];
pushdown(v,k,l,r);
int mid=(l+r)>>;
if (y<=mid) return query(v<<,l,mid,x,y,k); else
if (x>mid) return query(v<<|,mid+,r,x,y,k); else
return query(v<<,l,mid,x,mid,k)+query(v<<|,mid+,r,mid+,y,k);
}
int main(){
scanf("%d%d",&n,&m);
scanf("%s",s+);
build(,,n);
for (int i=;i<=m;i++){
scanf("%d%d%d",&l,&r,&x);
int now=l;
if (x){
for (int j=;j<;j++){
int t=query(,,n,l,r,j);
if (!t) continue;
change(,,n,l,r,j,);
change(,,n,now,now+t-,j,);
now+=t;
}
} else{
for (int j=;j>=;j--){
int t=query(,,n,l,r,j);
if (!t) continue;
change(,,n,l,r,j,);
change(,,n,now,now+t-,j,);
now+=t;
}
}
}
for (int i=;i<=n;i++)
for (int j=;j<;j++)
if (query(,,n,i,i,j)){
printf("%c",j+'a');
break;
}
return ;
}