codeforces 558 E. A Simple Task (线段树优化计数排序)
题意：给出一个字符串，仅由小写字母组成。现在给出q个操作，每个操作l,r,k三个参数，k=1表示把区间[l,r]变为升序排列，k=0表示把区间[l,r]变为降序排列。
思路：首先，最重要的一点是，由于只有26个字母，联想到计数排序。
对于字符集数目比较小情况，一定要想到计数排序。
对于字符集数目比较小情况，一定要想到计数排序。
对于字符集数目比较小情况，一定要想到计数排序。
那么我们回顾计数排序，不妨考虑升序排列的情况，是怎么做的呢？
做法是统计该区间中每种字符的个数，然后按照字符的大小，从小到大在区间上从左到右得放置每种字符。
大概是这样子：
for(int j=x;j<=y;j++)
cnt[s[j] - 'a']++;
ind = 0;
for(int j=x;j<=y;j++)
{
while(cnt[ind] == 0)
ind++;
s[j] = ind + 'a';
cnt[ind]--;
}
然而这个复杂度每次是o(n)的。。。
我们需要用线段树来优化计数排序的过程。。。
思考计数排序其实分为两个过程：
一是统计某区间中每个字符的个数。
二是将字符按照字符的大小顺序重新放回区间。
我们可以建26棵线段树，一种字母对应一棵。
对于过程一，我们可以直接query.
对于过程2，由于相同的字母总是相邻在一起的，因此可以用线段树成段更新来优化，也就是lazy标记。
tree[id][rt]表示第id棵线段树对应的区间中字母id+'a'-1的个数。
lazy[id][rt]三种值，-1表示没有标记，0表示重置标记，1表示被某种字母覆盖的标记。（重置的意思是，该区间被排序了，但是还不确定该区间上字母是哪些）
输出的时候，对于某个位置，只要query到26个字母中值不为0的那个输出就好了。
总的复杂度：O(26qlgn)
代码注释中还有部分细节和理解
/* ***********************************************
Author :111qqz
Created Time :2016年10月04日 星期二 23时59分11秒
File Name :code/cf/problem/558E.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <deque>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <bitset>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
int tree[27][N<<2];//26棵线段树，表示26个字母在对应区间中的个数。
int lazy[27][N<<2];//lazy存储的是某段区间是否被某个字母覆盖. -1表示初始没有标记，0表示该区间被重置，1表示该区间被某种颜色覆盖。
int n,q;
char st[N];
int cnt[27]; //计数排序.
void PushUp(int rt,int id)
{
tree[id][rt] = tree[id][rt<<1] + tree[id][rt<<1|1];
}
void PushDown(int l,int r,int rt,int id)
{
if (lazy[id][rt]==-1) return ;
if (l==r) return;
lazy[id][rt<<1] = lazy[id][rt<<1|1] = lazy[id][rt]; //可以把一段区间被某种字母覆盖看做被染色。。。不过我们不需要知道被哪种字母染色，只需要知道是否被染色。
if (lazy[id][rt]) //如果一段区间被某种字母覆盖，那么该区间某种字母的数目就是区间长度，这也是PushDown需要传递区间端点l,r进来的原因。
{
int m = (l+r)>>1;
tree[id][rt<<1] = m-l+1;
tree[id][rt<<1|1] = r-m; //区间长度
}
else tree[id][rt<<1] = tree[id][rt<<1|1] = 0 ; //如果被重置了，清空线段树数组。
lazy[id][rt] = -1;
//关于lazy标记的思考：lazy标记是为了延迟更新。。。因此PushDown操作的内容其实和update时候的东西是非常相似的。。。
}
void build ( int l,int r,int rt)
{
if (l==r)
{
int id = st[l]-'a'+1;
tree[id][rt] = 1;
lazy[id][rt] = 1;
return;
}
int m = (l+r)>>1;
build(lson);
build(rson);
for ( int i = 1 ; i <= 26 ; i++) //26棵线段树，每一层向上更新的时候每一棵都要记得更新。
PushUp(rt,i);
}
void update(int L,int R,int sc,int l,int r,int rt,int id)
{
if (L<=l&&r<=R)
{
lazy[id][rt] = sc; //sc为0表示重置区间，sc为1表示该区间被id+'a'-1的字母覆盖。
if (sc) tree[id][rt] = r-l+1;
else tree[id][rt] = 0;
return;
}
PushDown(l,r,rt,id);
int m = (l+r)>>1;
if (L<=m) update(L,R,sc,lson,id);
if (R>=m+1) update(L,R,sc,rson,id);
PushUp(rt,id);
}
int query(int L,int R,int l,int r,int rt,int id)
{
if (L<=l&&r<=R) return tree[id][rt];
PushDown(l,r,rt,id);
int m = (l+r)>>1;
int ret = 0 ;
if (L<=m) ret = ret + query(L,R,lson,id);
if (R>=m+1) ret = ret + query(L,R,rson,id);
PushUp(rt,id);
return ret;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
ms(tree,0);
ms(lazy,-1);
cin>>n>>q;
scanf("%s",st+1);
build(1,n,1);
while (q--)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
for ( int i = 1 ; i <= 26 ; i++)
{
cnt[i] = query(l,r,1,n,1,i);
update(l,r,0,1,n,1,i); //初始要把[l,r]区间的每个字母的线段树区间重置，因为排序会打乱，在下面按照k的不同以不同方式（正序，逆序）更新。
}
if (k==1)
{
int pos = l;
for ( int i = 1 ; i <= 26 ; i++)
{
if (cnt[i]==0) continue;
update(pos,pos+cnt[i]-1,1,1,n,1,i);
pos = pos + cnt[i];
}
}
else
{
int pos = l;
for ( int i = 26 ; i >= 1 ; i--)
{
if (cnt[i]==0) continue;
update(pos,pos+cnt[i]-1,1,1,n,1,i);
pos = pos + cnt[i];
}
}
}
for ( int i = 1 ; i <= n ; i++)
{
for ( int j = 1 ; j <= 26 ; j++)
{
if (query(i,i,1,n,1,j)) //在第i个位置26个字母只可能有一种值为1，其余都为0，输出的时候query就好了。
{
printf("%c",j+'a'-1);
break;
}
}
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}