这题目的原题是CF 558E但是加强了。 问题非常简单，给定一个长度为n的字符串S，有q个操作，每次操作的形式为 i j k，表示对从i到j的这一段子串进行排序，如果k=1进行非降序排序，否则进行非升序排序。 输出最后的字符串。 样例解释：
Input 单组测试数据。 第一行有两个整数n, q (1 ≤ n ≤ 10^5, 0 ≤ q ≤ 50 000)，表示字符串的长度和操作次数。 第二行有一个字符串。只由小写字母组成。 接下来q行，每行包含三个整数 i,j,k(1 ≤ i ≤ j ≤ n, k∈{0,1})。 Output 输出最后的字符串。 Input示例 10 5 abacdabcda 7 10 0 5 8 1 1 4 0 3 6 0 7 10 1 Output示例 cbcaaaabdd 这道题有两种算法，一种是splay维护，比较复杂但是跑的飞快，另一种就是26棵线段树直接莽一波，比较暴力而且简单，就是细节比较复杂。 线段树维护的是：26个字母中排第i个的字母在各个区间的数目。 这样一来，我们就可以将一个字符串S完美的融入到这26棵线段树中去，更新和查找都从上面的O(n)变为了O(logn)。 下面贴出核心代码：
int main() { int i,j,k; scanf("%d%d",&n,&q); scanf("%s",s); for(i=0;i<q;i++) scanf("%d%d%d",&l[i],&r[i],&c[i]); memset(a,-1,sizeof(a)); for(i=1;i<26;i++) { build(1,n,i,1); for(j=0;j<q;j++) { k=qz(1,n,l[j],r[j],1); if(c[j]) { update(1,n,l[j],r[j]-k,0,1); update(1,n,r[j]-k+1,r[j],1,1); } else { update(1,n,l[j],l[j]+k-1,1,1); update(1,n,l[j]+k,r[j],0,1); } } for(j=0;j<n;j++) { k=query(1,n,j+1,1); if(!k&&a[j]==-1) a[j]='a'+i-1; } } for(j=0;j<n;j++) { if(a[j]==-1) a[j]='z'; } a[n]=0; printf("%s\n",a); return 0; }剩余的都是一些线段树的操作，例如释放标记啊之类的，主要就是这里了吧。 想知道splay怎么做的加51nod的Q群251587768（我绝对不是在卖广告，里面都是大神。）
