[20190927机房测试] string

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

看到针对序列的操作，还以为是什么高级的算法
比如Splay啦，Spaly啦，Splay啦……
结果是（几）棵裸的线段树？
而且还非常暴力？？？

因为只有26种小写字母，所以直接开26棵线段树
每棵线段树统计一个区间内对应字母的出现次数
操作的时候直接按顺序把统计了次数的字母填进去就完了

#include<bits/stdc++.h>
#define N 100005
#define t tr[opt]
using namespace std;
int n,m,num[26],opt;
char ch[N];

struct T
{
	int sum[N<<2],sign[N<<2];
}tr[26];

template <class T>
void read(T &x)
{
	char c;int sign=1;
	while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
	while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}

inline void pushup(int rt)
{
	t.sum[rt]=t.sum[rt<<1]+t.sum[rt<<1|1];
}
void add_sign(int rt,int l,int r,int val)//将[l,r]赋值为val 
{
	t.sum[rt]=(r-l+1)*val;
	t.sign[rt]=val;
}
void pushdown(int rt,int l,int r)
{
	if(t.sign[rt]==-1) return;
	int mid=(l+r)>>1;
	add_sign(rt<<1,l,mid,t.sign[rt]);
	add_sign(rt<<1|1,mid+1,r,t.sign[rt]);
	t.sign[rt]=-1;
}
void modify(int rt,int l,int r,int x,int y,int val)
{
	if(x<=l&&r<=y) return add_sign(rt,l,r,val);
	int mid=(l+r)>>1;
	pushdown(rt,l,r);
	if(x<=mid) modify(rt<<1,l,mid,x,y,val);
	if(y>mid) modify(rt<<1|1,mid+1,r,x,y,val);
	pushup(rt);
}
int query(int rt,int l,int r,int x,int y)
{
	if(x<=l&&r<=y) return t.sum[rt];
	int mid=(l+r)>>1,ret=0;
	pushdown(rt,l,r);
	if(x<=mid) ret+=query(rt<<1,l,mid,x,y);
	if(y>mid) ret+=query(rt<<1|1,mid+1,r,x,y);
	return ret;
}
void build(int rt,int l,int r)
{
	for(int i=0;i<26;++i) tr[i].sign[rt]=-1;
	if(l==r)
	{
		tr[ch[l-1]-'a'].sum[rt]=1;
		return;
	}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	for(int i=0;i<26;++i) tr[i].sum[rt]=tr[i].sum[rt<<1]+tr[i].sum[rt<<1|1];
}

int main()
{
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	read(n);read(m);
	scanf("%s",ch);
	build(1,1,n);
	while(m--)
	{
		int l,r,k;
		read(l);read(r);read(k);
		for(int i=0;i<26;++i)
		{
			opt=i;
			num[i]=query(1,1,n,l,r);
			modify(1,1,n,l,r,0);
		}
		if(k==1)//升序 
		{
			for(int i=0;i<26;++i)
			{
				opt=i;
				if(num[i]) modify(1,1,n,l,l+num[i]-1,1);
				l+=num[i];
			}
		}
		else//降序 
		{
			for(int i=25;i>=0;--i)
			{
				opt=i;
				if(num[i]) modify(1,1,n,l,l+num[i]-1,1);
				l+=num[i];
			}
		}
	}
	for(int i=1;i<=n;++i)
		for(int j=0;j<26;++j)
		{
			opt=j;
			if(query(1,1,n,i,i))
			{
				printf("%c",(char)(j+'a'));
				break;
			}
		}
	printf("
");
	return 0;
}
/*
25 10
alskslaklksalakslsaksalks
15 16 1
11 20 0
1 20 1
2 4 0
4 5 1
5 6 1
7 11 0
9 17 0
1 1 1
1 7 0
lkaaaaakssllllkkkssssalks
*/