题意

本题要求对一个字符串的某个区间进行排序操作。具体来说，对于每个查询，需要将区间 $[x, y]$ 内的字符按字母顺序重新排列（升序）。要求设计一个高效的数据结构来支持这种操作。

思路

最直接的方法是使用计数排序：对于每个查询，统计区间内每个字符的出现次数，然后按顺序重新填充区间。但这种方法的时间复杂度为 $O(n)$ 每次查询，对于大数据量来说太慢。

优化思路是使用 $26$ 棵线段树，每棵线段树对应一个小写字母（$a$ 到 $z$）。对于每个查询：

1. 在区间 $[x, y]$ 内，分别查询 $26$ 棵线段树，得到每个字符的出现次数。
2. 根据这些计数，按字母顺序重新分配区间内的字符。
3. 使用懒标记（lazy propagation）技术更新每棵线段树中对应区间的值。

算法步骤

1. 构建 $26$ 棵线段树，每棵线段树维护原字符串中对应字符的出现位置（用 $1$ 表示该位置是该字符，$0$ 表示不是）。
2. 对于每个查询 $[x, y]$：
   • 遍历 $26$ 个字符，分别查询每棵线段树在区间 $[x, y]$ 内的和，得到每个字符的计数 $cnt[0..25]$。
   • 将区间 $[x, y]$ 内所有字符对应的线段树区间值置为 $0$（清空该区间）。
   • 按字母顺序，依次将每个字符的计数个 $1$ 填充回区间 $[x, y]$ 中对应的位置（使用区间更新）。
3. 所有查询结束后，遍历 $26$ 棵线段树，根据每个位置上的 $1$ 还原出最终的字符串。

复杂度分析

• 时间复杂度：每次查询需要 $O(26 \log n)$ 来获取计数，以及 $O(26 \log n)$ 来更新线段树，因此总时间复杂度为 $O(26 \cdot q \log n)$，其中 $q$ 是查询次数，$n$ 是字符串长度，$26$ 是字母表大小。
• 空间复杂度：$O(26 \cdot n)$，用于存储 $26$ 棵线段树。

代码说明

• 使用 $26$ 个线段树对象，每个对象维护一个字符的区间和。
• 查询时，先通过区间求和得到每个字符的计数。
• 更新时，先将整个区间清空（所有字符的线段树对应区间置 $0$），然后按字母顺序依次将每个字符的计数个 $1$ 更新到区间中。
• 使用懒标记（lazy tag）来优化区间更新操作，避免逐点更新。
• 最终通过遍历每个位置，检查 $26$ 棵线段树在该位置的值，确定该位置的字符。

#include <bits/stdc++.h>
using namespace std;
 
inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}
 
const int N=1e5+5;
 
int n,m,ans;
char ch[100001],res[100001];
 
struct seg
{
	int tr[31][400001],laz[31][400001];
	inline void init()
	{
		for ( int i=1;i<=26;i++ )  
			memset(laz[i],-1,sizeof(laz[i]));
	}
	inline void build(int rt,int l,int r)
	{
		if(l==r)
		{
			tr[ch[l]-'a'+1][rt]=1;
			return;
		}
		int mid=(l+r)/2;
		build(rt<<1,l,mid);
		build(rt<<1|1,mid+1,r);
		for ( int i=1;i<=26;i++ ) 
			tr[i][rt]=(tr[i][rt<<1]+tr[i][rt<<1|1]);
	}
	inline void push_down(int rt,int l,int r,int col)
	{
		if(laz[col][rt]!=-1)
		{
			tr[col][rt]=laz[col][rt]*(r-l+1);
			int mid=(l+r)/2;
			tr[col][rt<<1]=laz[col][rt]*(mid-l+1);
			tr[col][rt<<1|1]=laz[col][rt]*(r-mid);
			laz[col][rt<<1]=laz[col][rt];
			laz[col][rt<<1|1]=laz[col][rt];
			laz[col][rt]=-1;
		}
	}
	inline void update(int rt,int l,int r,int ll,int rr,int col,int v)
	{
		if(ll<=l&&r<=rr)
		{
			tr[col][rt]=v*(r-l+1);
			laz[col][rt]=v;
			return;
		}
		push_down(rt,l,r,col);
		int mid=(l+r)/2;
		if(ll<=mid) update(rt<<1,l,mid,ll,rr,col,v);
		if(rr>mid) update(rt<<1|1,mid+1,r,ll,rr,col,v);
		tr[col][rt]=tr[col][rt<<1]+tr[col][rt<<1|1];
	}
	inline int query(int rt,int l,int r,int ll,int rr,int col)
	{
		if(ll<=l&&r<=rr) return tr[col][rt];
		push_down(rt,l,r,col);
		int mid=(l+r)/2;
		int sum=0;
		if(ll<=mid) sum+=query(rt<<1,l,mid,ll,rr,col);
		if(rr>mid) sum+=query(rt<<1|1,mid+1,r,ll,rr,col);
		return sum;
	}
	inline void print(int rt,int l,int r)
	{
		if(l==r)
		{
			for ( int i=1;i<=26;i++ ) 
				if(tr[i][rt]) 
				{
					res[l]='a'+i-1;
					break;
				}
			return;
		}
		for ( int i=1;i<=26;i++ ) push_down(rt,l,r,i);
		int mid=(l+r)/2;
		print(rt<<1,l,mid);
		print(rt<<1|1,mid+1,r);
	}				
};
seg T;
 
int main()
{
	n=read();
	m=read();
	scanf("%s",ch+1);
	T.init();
	T.build(1,1,n);
	for (;m--;)
	{
		int op,x,y;
		x=read(),y=read(),op=read();
		if(op==1)
		{
			int tmp=x-1;
            for ( int j=1;j<=26;j++ )
			{
                int cas=T.query(1,1,n,x,y,j);
                if(!cas)continue;
                T.update(1,1,n,x,y,j,0);
                T.update(1,1,n,tmp+1,tmp+cas,j,1);
				tmp=tmp+cas;
            }
		}
		else
		{
			int lp=x-1;
			for ( int j=26;j>=1;j-- )
			{
				int sum=T.query(1,1,n,x,y,j);
				if(!sum) continue;
				T.update(1,1,n,x,y,j,0);
				T.update(1,1,n,lp+1,lp+sum,j,1);
				lp+=sum;

			}
		}
	}
	T.print(1,1,n);
	for ( int i=1;i<=n;i++ ) putchar(res[i]);
	return 0;
}
/*
10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1
*/