题目链接：
http://codeforces.com/problemset/problem/558/E
E. A Simple Task
time limit per test5 secondsmemory limit per test512 megabytes
#### 问题描述
> This task is very simple. Given a string S of length n and q queries each query is on the format i j k which means sort the substring consisting of the characters from i to j in non-decreasing order if k = 1 or in non-increasing order if k = 0.
>
> Output the final string after applying the queries.
输入
The first line will contain two integers n, q (1 ≤ n ≤ 105, 0 ≤ q ≤ 50 000), the length of the string and the number of queries respectively.
Next line contains a string S itself. It contains only lowercase English letters.
Next q lines will contain three integers each i, j, k (1 ≤ i ≤ j ≤ n, ).
输出
Output one line, the string S after applying the queries.
样例输入
10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1
样例输出
cbcaaaabdd
题意
给你一个长度为n的字符串（只有小写字母），m个更新操作（l,r,type）要么对区间里面的字符串升序排，要么降序排，问m个更新之后最后的字符串是什么
题解
首先，只有26个字母，可以考虑计数排序，其次，当然是要用线段树来维护了，可以开26颗线段树，支持区间更新，区间查询。
对于更新区间先查询一下各个字母多少个，然后再按排完序的结果，26个字母（对应26颗线段树）全部干一发区间更新。
代码
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf
typedef __int64 LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;
const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0);
//start----------------------------------------------------------------------
const int maxn=1e5+10;
int sumv[26][maxn<<2],setv[26][maxn<<2];
int n,m;
char str[maxn];
void maintain(int id,int o) {
sumv[id][o]=sumv[id][lson]+sumv[id][rson];
}
void pushdown(int id,int o,int l,int r) {
if(setv[id][o]<0) return;
sumv[id][lson]=(mid-l+1)*setv[id][o];
sumv[id][rson]=(r-mid)*setv[id][o];
setv[id][lson]=setv[id][rson]=setv[id][o];
setv[id][o]=-1;
}
void build(int id,int o,int l,int r) {
if(l==r) {
int idx=str[l]-'a';
if(id==idx) sumv[id][o]=1;
else sumv[id][o]=0;
} else {
build(id,lson,l,mid);
build(id,rson,mid+1,r);
maintain(id,o);
}
}
int ul,ur,uv;
void update(int id,int o,int l,int r) {
if(ul<=l&&r<=ur) {
sumv[id][o]=(r-l+1)*uv;
setv[id][o]=uv;
} else {
pushdown(id,o,l,r);
if(ul<=mid) update(id,lson,l,mid);
if(ur>mid) update(id,rson,mid+1,r);
maintain(id,o);
}
}
int ql,qr,qv;
void query(int id,int o,int l,int r) {
if(ql<=l&&r<=qr) {
qv+=sumv[id][o];
} else {
pushdown(id,o,l,r);
if(ql<=mid) query(id,lson,l,mid);
if(qr>mid) query(id,rson,mid+1,r);
maintain(id,o);
}
}
void init() {
clr(sumv,0);
clr(setv,-1);
}
int main() {
init();
scf("%d%d",&n,&m);
scf("%s",str+1);
rep(i,0,26) build(i,1,1,n);
rep(i,0,m) {
int l,r,type;
scf("%d%d%d",&l,&r,&type);
int lef=l;
if(type==1) {
rep(i,0,26) {
ql=l,qr=r,qv=0;
query(i,1,1,n);
ul=l,ur=r,uv=0;
update(i,1,1,n);
ul=lef,ur=lef+qv-1,uv=1;
if(ul<=ur) update(i,1,1,n);
lef+=qv;
}
} else {
for(int i=25; i>=0; i--) {
ql=l,qr=r,qv=0;
query(i,1,1,n);
ul=l,ur=r,uv=0;
update(i,1,1,n);
ul=lef,ur=lef+qv-1,uv=1;
if(ul<=ur){
// prf("(%d,%d),id:%d\n",ul,ur,i);
update(i,1,1,n);
}
lef+=qv;
}
}
}
for(int i=1;i<=n;i++){
rep(j,0,26){
ql=i,qr=i,qv=0;
query(j,1,1,n);
if(qv>0){
prf("%c",'a'+j);
break;
}
}
}
puts("");
return 0;
}
//end-----------------------------------------------------------------------
/*
10 1
abacdabcda
7 10 0
*/
Notes
以后需要建多颗线段树的时候最好把它们所有的操作都独立开，不要放在一起！因为放在一起反而有可能变麻烦。