Description：

一个由小写字母组成的字符串 $ s$ 。有 $ m $ 次操作，每次操作给定 $ 3 $ 个参数 $ l,r,x$ 。如果 $x=1$ ，将 $ s[l]$ ~ $s[r]$ 升序排序；如果 $ x=0$ ，将 $ s[l]$ ~ $s[r] $ 降序排序。你需要求出最终序列。

$1\le n \le 100000$

Solution：

发现字母数只有 $26$ ，于是开 $26$ 棵线段树，维护区间个数，每次操作时就查询 $26$ 个数的出现个数并把它们依次按顺序插进原树中，时间复杂度 $O(26\times nlog_2n)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

#pragma GCC optimize(2)

using namespace std;

int n,m;

#define MAXN 100010

inline int getc()

{

	register char c = getchar();

	while(c < 'a' || c > 'z')c = getchar();

	return (int)(c - 'a');

}

struct node

{

	int lc,rc;

	int s[26];

	int tag[26];

}t[MAXN << 1];

int ptr = 0;

inline int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

inline void pushdown(int rt,int k,int l,int r)

{

	if(t[rt].tag[k] == -1)return;

	t[t[rt].lc].tag[k] = t[t[rt].rc].tag[k] = t[rt].tag[k];

	t[t[rt].lc].s[k] = (mid - l + 1) * t[rt].tag[k];

	t[t[rt].rc].s[k] = (r - mid) * t[rt].tag[k];

	t[rt].tag[k] = -1;

	return;

}

void set(int rt,int L,int R,int k,int l,int r)

{

	if(L > R)return;

	if(L <= l && r <= R)

	{

		t[rt].tag[k] = 1;

		t[rt].s[k] = r - l + 1;

		return;

	}

	if(t[rt].tag[k] != -1)pushdown(rt,k,l,r);

	if(L <= mid)set(t[rt].lc,L,R,k,l,mid);

	if(R > mid)set(t[rt].rc,L,R,k,mid + 1,r);

	t[rt].s[k] = t[t[rt].lc].s[k] + t[t[rt].rc].s[k];

	return;

}

int sum[26];

void getsum(int rt,int L,int R,int l,int r)

{

	if(L > R)return;

	if(L <= l && r <= R)

	{

		for(register int i = 0;i < 26;++i)

		{

			sum[i] += t[rt].s[i];

			t[rt].s[i] = t[rt].tag[i] = 0;

		}

		return;

	}

	for(register int i = 0;i < 26;++i)if(t[rt].tag[i] != -1)pushdown(rt,i,l,r);

	if(L <= mid)getsum(t[rt].lc,L,R,l,mid);

	if(R > mid)getsum(t[rt].rc,L,R,mid + 1,r);

	for(register int i = 0;i < 26;++i)t[rt].s[i] = t[t[rt].lc].s[i] + t[t[rt].rc].s[i];

	return;

}

void pt(int rt,int l,int r)

{

	for(int i = 0;i < 25;++i)

	{

		if(t[rt].tag[i] == 1)

		{

			for(int k = l;k <= r;++k)putchar(i + 'a');

			return;

		}

	}

	if(l == r)

	{

		for(register int i = 0;i < 26;++i)

			if(t[rt].s[i] != 0){putchar(i + 'a');break;}

		return;

	}

	for(register int i = 0;i < 26;++i)pushdown(rt,i,l,r);

	pt(t[rt].lc,l,mid);

	pt(t[rt].rc,mid + 1,r);

	return;

}

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + (c ^ 48);

		c = getchar();

	}

	return res;

}

int main()

{

	freopen("string.in","r",stdin);

	freopen("string.out","w",stdout);

	n = read();m = read();

	build(root,1,n);

	for(register int i = 1;i <= n;++i)set(root,i,i,getc(),1,n);

	register int l,r,v;

	for(register int i = 1;i <= m;++i)

	{

		l = read();r = read();v = read();

		memset(sum,0,sizeof(sum));

		getsum(root,l,r,1,n);

		if(v == 1)

			for(register int k = 0,cur = l;k < 26;cur += sum[k],++k)

				set(root,cur,cur + sum[k] - 1,k,1,n);

		else

			for(register int k = 25,cur = l;k >= 0;cur += sum[k],--k)

				set(root,cur,cur + sum[k] - 1,k,1,n);

	}

	pt(root,1,n);puts("");

	fclose(stdin);

	fclose(stdout);

	return 0;

}